形式语言与自动机第二课

语言以及文法

主要内容：

1. 形式语言有关术语
2. 文法的定义、分类

字母表与字符串

字母表

• 字母表：字符的有限集合（不允许出现相同的字符）
  常用$T$、$\sum$表示

• 字母表的幂运算
  归纳定义：

1. T0={ϵ}T^0=\{\epsilon\}T0={ϵ}
2. $x\in T^{n-1},a\in T$=>$ax\in T^n$
3. $T^n$的元素只能由1、2生成

字母表的$\ast$闭包：$T^{\ast }=T^0\cup T^1\cup T^2......$：所有字符串和空串的集合
$+$闭包：$T^{+}=T^1\cup T^2\cup T^3......$：所有字符串（不包括空串）的集合
T∗=T+∪{ϵ}T^*=T^+\cup\{\epsilon\}T∗=T+∪{ϵ}
T+=T∗−{ϵ}T^+=T^*-\{\epsilon\}T+=T∗−{ϵ}

字符串

• 字符串：字母表中的字符构成的序列（常记为u、v、w、x、y、z）

1. 使用 $ϵ$ 表示空串
2. 字符串$w$的宽度记作$|w|$
3. $a^i$代表含有$i$个$a$的字符串

• 字符串的连接

1. 写法：$xy$
2. 性质：$(xy)z=x(yz)$、$ϵx=xϵ=x$、$|xy|=|x|+|y|$

空串是任何字符串的前缀、后缀、子串

• 字符串的逆：$\overline{w}$

语言

语言是字母表的$T^{\ast }$的子集=>语言是集合
$L\subset T^{\ast }$

空语言：$\Phi$

对于集合的运算可以应用于对语言的计算

• 语言的积：
  语言的积是语言中的字符串相连接所构成的集合
  语言的积不可交换：$L_1{L}_2!=L_2{L}_1$

• 语言的幂

1. L0={ϵ}L^0=\{\epsilon\}L0={ϵ}
2. $L^n=L{L}^{n-1}$

文法（重点）

文法是定义语言的数学模型
当语言L是无限集合时：

1. 文法产生系统，由文法产生语言的句子
2. 机器识别系统，当一个字符串能被一个语言的识别系统识别，则属于该语言，否则不属于该语言

元语言：讨论对象语言的语言
对象语言：被讨论的语言

文法就是元语言

BNF（巴科斯范式）

BNF范式一般作为元语言

一种BNF对标识符的定义：

• $<数字>::=0|1|2|...9$
• $<字母>::=A|B|C|...Z|a|b|...z$
• $<标识符>::=<字母>|<标识符><字母>|<标识符><数字>$

Chomsky文法体系（重点）

将$::=$改为$\to$表示可被代替
使用$I、L、D$表示标识符、字母、数字

==>
$I\to L$
$I\to IL$
$I\to ID$
$L\to a|b...|z$
$D\to 0|1...|9$
一个文法的生成式集合

N={I、L、D}N=\{I、L、D\}N={I、L、D}
T={a,b,c,...,z,0,1,2,...,9}T=\{a, b, c, ..., z, 0, 1, 2, ..., 9\}T={a,b,c,...,z,0,1,2,...,9}
P={I,La,...,D0,...,D9}P=\{I, L_a, ..., D_0, ..., D_9\}P={I,La​,...,D0​,...,D9​}
$S=I$

生成式集合是文法的核心

在这个体系中

1. 任何一种文法必须包含两个不同的有限符号的集合，即非终结符集合N（不会在句子中出现）、终结符集合T，还有生成式集合与起始符
2. 形式规则的有限集合P（生成式集合）：产生语言句子的规则
3. 句子：仅由终结符产生的字符串。它们必须从一个起始符S开始，不断使用P中的生成式进行推导

$G=(N,T,P,S)$
$G$：文法
$N$：非终结符的有限集合
$T$：终结符的有限集合，N、T无交集
$P$：形式为$\alpha \to \beta$的有限集合，$\alpha$是N、T的组合，但是不能是空串，$\beta$是N、T的组合
$S$：起始符，$S\in N$

推导、句型

• 直接推导
  $G=(N,T,P,S)$，$A\to \beta$ 是$P$的生成式，$\alpha 、\gamma$是$(N\cup T{)}^{\ast }$的字符串，则$\alpha A\gamma \to \alpha \beta \gamma$，称$\alpha A\gamma$直接推导出$\alpha \beta \gamma$

• 推导序列
  $G=(N,T,P,S)$，${\alpha }_i$是$(N\cup T{)}^{\ast }$的字符串，且${\alpha }_i$直接推导处${\alpha }_{i+1}$，称${\alpha }_0=>{\alpha }_1=>{\alpha }_2=>...{\alpha }_n$为长度为n的推导序列（推导n次），
  ${\alpha }^{\prime }={\alpha }_n$，$\alpha ={\alpha }_0$，$\alpha$推导出${\alpha }^{\prime }$写作
  $$\alpha {\to }_G^{\ast }{\alpha }^{\prime }$$
  推导序列长度大于0，记作
  $$\alpha {\to }_G^{+}{\alpha }^{\prime }$$
  推导序列的每一步都产生一个字符串，称之为句型（可能包含终结符也可能包含非终结符）

• 句型
  $\alpha$是文法$G$的句型<=>$S{\to }_G^{\ast }\alpha$，$\alpha \in (N\cup T{)}^{\ast }$
  句型可能包含非终结符

• 句子
  $w$是$G$的句子<=>$S{\to }_G^{\ast }w$，$w\in T^{\ast }$
  句子不包含非终结符

句型包含句子

• 文法产生的语言
  由文法G产生的语言记为$L(G)$
  L(G)={w∣w∈T∗,S→G∗w}L(G)=\{w|w\in T^*, S\rightarrow^*_Gw\}L(G)={w∣w∈T∗,S→G∗​w}
  即句子的集合：必然由终结符组成，必然由起始符S推导

分类（重点）

该体系对生成式的形式作出了一些规定：0型、1型、2型、3型

• 0型：无限制文法
  对应的语言：递归可枚举语言，等同于图灵机

• 1型：上下文有关文法
  生成式：$\alpha \to \beta$
  其中$|\alpha |<=|\beta |$，$\beta$不为空串
  对应的语言：上下文有关语言，不考虑空串，则与线性有界自动机等价

• 2型：上下文无关文法
  生成式：$A\to \beta$，左侧为单个符号，非终结符
  对应语言：上下文无关语言
  对应自动机：下推自动机

• 3型：正则文法
  分为右线性文法与左线性文法
  $A\to wB$、$A\to Bw$
  $A、B\in N$， $w\in T^{\ast }$
  对应的语言：正则语言
  对应的自动机：有限自动机

例子
G=({A,B,C},{a,b,d},P,A)G=(\{A,B,C\},\{a,b,d\},P,A)G=({A,B,C},{a,b,d},P,A)
$P:A\to AB$、$AB\to CAAB$、$A\to d$、$B\to a$、$C\to b$
是上下文有关文法

• 四类文法的关系

1. 0型：无限制
2. 1型，左边长度小于等于右边。右边不允许是空串
3. 2型，左边是非终结符、单个符号
4. 3型，左边是非终结符、单个字符，右边是$wB$、$Bw$或者$w$
5. 1、2、3属于0型
6. 不含$A\to ϵ$的2、3型属于1型
7. 3型属于2型

总结