形式语言

形式语言

用计算机处理语言要考虑语言的形式化与规范化,使其具有可计算性和可操作性

如何把语言形式化这就是形式语言理论研究的问题

形式语言诞生于1956年,由 Chomsky 创立

通常研究涉及到

  • 语法
  • 语义
  • 语用

基本观点

把语言用符号串表示

研究它如何用符号串表示 ,研究分析他的结构特性,运算规律

定义

形式语言是符号串的集合

是至目标上的符号按照一定的规则组成的所有符号串的集合

其中每个符号串成为一个句子

字母表

元素符号的非空有限集合

符号串

符号的有限序列

符号串集合

有限个或无限个符号串组成的集合

规则

以某种形式表达的在一定范围内共同遵守的章程和制度

这里指的是符号串的组成规则

运算

点连接

$\alpha . \beta = \alpha \beta$

或运算

$\alpha | \beta = \alpha 或者 \beta$

表示取其中一个符号

方幂

$\alpha ^n = \alpha \alpha \alpha … \alpha = \alpha \alpha ^{n-1} $

表示 n 个符号连接

空符号串

$\alpha ^0 = \epsilon $

闭包

正闭包

$\alpha ^+ = \alpha ^1 | \alpha ^2 | … | \alpha ^n | …$

星闭包

$\alpha ^* = \alpha ^0 | \alpha ^1 | \alpha ^2 | … | \alpha ^n | …$

符号串运算案例

$(a|b)^2 = (a|b)(a|b) = aa|bb|ab|ba$

符号串的运算

乘积

$AB = { xy | x属于A 且 y属于b }$

也就是说 从 A取出一个符号串 再从B取出一个符号串

$A并B = A+B$

A和B集合的元素加在一起

方幂

类似

闭包

类似符号串

文法

描述方式

描述形式语言有多种方式

  • 枚举方式,当语言是有穷集合的时候可以这样做
  • 使用具体的文法描述

定义

文法 grammar 就是规则的有限集合,通常可以表示为四元组

$G(Z)=V_N, V_T, Z, P$

$V_N$

非终结符集合(定义的对象集合,例如:语法成分)

$V_T$

终结符集(字母表)

Z

开始符号(研究范畴中最大的定义对象)

也就是我们推导一个句子的起始符号

P

规则集(产生式集)

终结符产生式

通常是带有 $\epsilon$ 符号的产生式

推导

从 开始符号 开始,选择一个产生式,把非终结符按照那个产生式推导出非终结符

一直这样推导下去,直到把所有的符号都推导成终结符,最后就推导出了一个句子

产生式

也就是通过一个非终结符产生另一个符号串,这个符号串可以是终结符也可以是非终结符

例如下面这个产生式
$$
S -> aAc
A -> bA | \epsilon
$$
就可以推导出如下符号串
$$
abc,abbc,abbbc…
$$

举例

语言

一个文法所定义的语言,就是由该文法开始符号推导出的所有仅含终结符的所有符号串的集合。其中每个符号串都称作句子。

从开始符号出发,对符号串中的定义对象,采用推导的方法(用它规则右部替换左部)产生新的符号串。如此进行,直到新符号串中不再出现定义的对象(非终极符)为止,则最终的符号串就是一个句子。

句型

一类句子的统称,通常是能够产生句子的产生式左端的那个非终结符

自动机

FA Finite Automata 有限自动机

可以处理正规语言

自动机里面的 1 2 3 4 等等圆圈成为状态集,每一个圆圈表示一个状态

其中 + 表示开始状态, - 表示结束状态

其中每条边上的字母,可以组成字母表

一个边连接的两个或者一个节点组成了一个状态转移,叫做变换,相当于应用了一条产生式

定义

  • Q 有限状态集
  • $\sum$ 字母表
  • S 开始状态
  • F 结束状态
  • $\delta$ 状态变换集

DFA确定有限自动机

某些特定情况下的正规语言表达,用传统的自动机表会有问题。

因此引入DFA来解决这个问题

定义

  • 开始状态唯一
  • 变换函数单值
  • 不带空(\epsilon)边

NFA非确定有限自动机

还区分带有空边和不带空边的NFA,前面加上 \epsilon

等价转换

有限自动机确定化

NFA 转换到 DFA

因为

NFA 较易构造,但不好用

DFA 较难构造,但是好用

任何一种 NFA 都可以通过有效算法转换成 DFA(等效转哈,二者描述的语言相通)

化简

有限自动机的最小化,构造一个等效的自动机,但是比之前的自动机状态更少

等价

如果两个状态看作初态,他们接受的符号串集合相同,则有等价

确定化算法

如果存在 空边 闭路,那么空边闭路上面的状态就可以和合并

然后 not epsilon NFD 转 DFA

最小化算法

确定化之后就没有 无用的状态 和 等价的状态

  • 无法被到达的状态 是 无用的状态

等价状态

  • 同是结束态或者非结束态
  • 对于字母表上所有符号,以他们作为起始状态,经过同样的符号都能变换到等价状态,那么他们就算等价状态

划分不同的等价状态

先划分出 结束状态集 和 非结束状态集

然后再观察,如果对于字母表里面某个符号进行状态转换,发现可以转换到不同的状态集,则分离分别划分

化简空边

  • 如果存在闭合的空边回路,则可以全部把空边连接的节点合而为一
  • 标记隐含的开始状态和结束状态,开始状态在空边的正向通路也都标记上开始状态,结束状态在空边的逆向通路标记结束状 态
  • 按照空边通路的逆向逐一删除,删除一个空边要引入新的边(凡是从原来空边的终点发出的边,也要从原来空边的起点发出指向那个终点)
  • 重复第三个步骤一直到没有空边为止

具体实现

查状态转移变换表实现

而状态转移表的数据结构如果使用传统的二维数组来实现,可能会出现浪费空间的现象,因为有些没有用到的数组成员也被分配了存储空间

可以使用多张索引表实现,状态指向转移字母条件(边),不同的边再指向不同的状态(按照这样分析,应该需要两张表,一张 {状态,状态转移表},另一张 {转移条件(含有字母的边),下一个应该转换到的目的状态})

正规语言表示方法

  • 正规文法
  • 正规式
  • 有限自动机FA

能用这三种方法表示的语言一定是正规语言

正规文法

用很多个产生式来定义

他有局限性,也就是
$$
L3 = { a^n b^n | n >= 0 }
$$
是无法被用正规文法表示的

正规式

正则表达式,也有类似于Windows通配符一样的表达式

正规式和状态机的转换

  • 或运算 转换成两条边
  • 乘积 级联
  • 闭包 级联 中间状态有一个自我转换的过程(实际过程中可以删掉空边)