1
形式语言和
自动机初步
2
第 11章 形式语言和自动机初步
? 11.1 形式语言和形式文法
? 11.2 有穷自动机
? 11.3 有穷自动机和正则文法的等价性
? 11.4 图灵机
3
? 字符串和形式语言
? 形式文法
? 形式文法的分类
? 0型文法
? 1型文法 或上下文有关文法
? 2型文法 或上下文无关文法
? 3型文法 或正则文法
11.1 形式语言与形式文法
4
语言的基本要素
汉语
字符,汉字和标点符号
字符集,合法字符的全体
句子,一串汉字和标点符号
语法,形成句子的规则
形式语言
字符
字母表
字符串
形式文法
5
字符串
字母表 Σ,非空的有穷集合
字符串, Σ中符号的有穷序列
如 Σ ={a,b}
a,b,aab,babb
字符串 ω的 长度 |ω|,ω中的字符个数
如 |a|=1,|aab|=3
空字符串 ε,长度为 0,即不含任何符号的字符串
an, n个 a组成的字符串
Σ*,Σ上字符串的全体
6
子字符串 (子串 ),
字符串中若干连续符号组成的字符串
前缀, 最左端的子串
后缀, 最右端的子串
例如 ω =abbaab
a,ab,abb是 ω的前缀
aab,ab,b是 ω的后缀
ba是 ω的子串,但既不是前缀,也不是后缀
ω本身也是 ω的子串,且既是前缀,也是后缀
ε也是 ω的子串,且既是前缀,也是后缀
7
字符串的连接运算
设 α=a1a2 … an,β= b1b2 … bm,
αβ=a1a2 … anb1b2 … bm称作 α与 β作的 连接
如 α=ab,β=baa,αβ=abbaa,βα=baaab
对任意的字符串 α,β,γ
(1) (αβ)γ=α(βγ)
即,连接运算满足结合律
(2) εα=αε=α
即,空串 ε是连接运算的单位元
n个 α的连接记作 αn
如 (ab)3= ababab,α0=ε
8
形式语言
定义, Σ*的子集称作字母表 Σ上的 形式语言,
简称 语言
例如 Σ={a,b}
A={a,b,aa,bb}
B={an | n∈ N}
C={anbm | n,m≥1}
D={ε}
空语言 ?
9
形式文法
一个例子 —— 标识符
<标识符 >, <字母 > | <下划线 > | <标识符 > <字母 > |
<标识符 > <下划线 >| <标识符 ><数字 >
<字母 >, a | b | … | z | A | B | … | Z
<下划线 >, _
<数字 >, 0 | 1 | … | 9
10
形式文法的定义
定义 形式文法 是一个有序 4元组 G=<V,T,S,P >,
其中
(1) V是非空有穷集合,V 的元素称作 变元 或 非终极符
(2) T是非空有穷集合且 V∩T =?,T 的元素称作 终极符
(3) S∈ V 称作 起始符
(4) P是非空有穷集合,P的元素称作 产生式 或 改写规则,
形如 α→ β,其中 α,β∈ (V∪ T)*且 α≠ε,
11
文法生成的语言
设文法 G = <V,T,S,P>,ω,λ∈ (V∪ T)*,
ω ?λ,存在 α→ β∈ P和 ξ,η∈ (V∪ T)*,使得
ω= ξαη,λ= ξβη
称 ω直接派生 出 λ,
ω λ,存在 ω1,ω2,…,ωm,使得
ω= ω1 ? ω2 ? … ? ωm= λ
称 ω派生 出 λ,
恒有 ω ω (当 m=1时 )
是 ? 的自反传递闭包
*
*
*
12
文法生成的语言
定义 设文法 G= <V,T,S,P >,G生成的语言
L(G)={ω∈ T* ∣ S ω}
L(G)由所有满足下述条件的字符串组成,
(1) 仅含终结符 ;
(2) 可由起始符派生出来,
定义 如果 L(G1)= L(G2),则称文法 G1与 G2等价,
*
13
举例
例 1 文法 G1= <V,T,S,P>,其中 V={S},T={a,b},
P,S→aSb | ab
L(G1)={anbn | n>0}
例 2 文法 G2= <V,T,S,P>,其中 V={A,B,S},T={0,1},
P,S→1 A,A→0 A | 1A | 0B,B→0
L(G2)={1x00 | x?{0,1}*}
例 3 文法 G3= <V,T,S,P>,其中 V={A,B,S},T={0,1},
P,S→B 0,B→A 0,A→A 1 | A0,A→1
L(G3)= L(G2),G3与 G2等价
14
例 4 G= <V,T,S,P>,其中 V={S,A,B,C,D,E},T={a},
P,(1) S→ACaB (2) Ca→aaC (3) CB→DB
(4) CB→E (5) aD→Da (6) AD→AC
(7) aE→Ea (8) AE→ ε
试证明, ?i ?1,S
证, a2 和 a4 的派生过程
S ? ACaB (1)
? AaaCB (2)
? AaaE (4)
? AEaa 2次 (7)
a2 (8) *
ia2
*
举例 (续 )
15
例 4 (续 )
S AaaCB
? AaaDB (3)
ADaaB 2次 (5)
? ACaaB (6)
AaaaaCB 2次 (2)
? AaaaaE (4)
AEaaaa 4次 (7)
? a4 (8)
*
*
*
*
16
例 4(续 )
先用归纳法证明 ?i ?1,
当 i=1 时结论成立,假设对 i 结论成立,
(3)
2i 次 (5)
(6)
2i 次 (2)
得证对 i +1 结论成立,故对所有的 i 成立,
CBAa i2
*
S
*
CBAa i2
DBAa i2
BA D a i2
BACa i2
CBAa i 12 ?
*
*
S
17
例 4 (续 )
于是,?i ?1,
(4)
2i 次 (7)
(8)
可以证明,
L(G) = { | i ?1} ia2
*
CBAa i2
EAa i2
iAEa 2
ia2
*
S
18
形式文法的分类
— Chomsky谱系
0型文法 (短语结构文法,无限制文法 )
1型文法 (上下文有关文法 ),
所有产生式 α→ β,满足 |α|?|β|
另一个等价的定义, 所有的产生式形如
ξAη→ ξαη
其中 A?V,ξ,η,α?(V∪ T)*,且 α?ε
2型文法 (上下文无关文法 ),
所有的产生式形如 A→ α
其中 A?V,α?(V∪ T)*,
19
形式文法的分类 (续 )
3型文法 (正则文法 ),右线性文法和左线性文法的统称
右线性文法, 所有的产生式形如
A→ αB 或 A→ α
左线性文法, 所有的产生式形如
A→ Bα 或 A→ α
其中 A,B?V,α?T*
例 1是上下文无关文法
例 2是右线性文法,例 3是左线性文法,都是正则文法
例 4是 0型文法
20
Chomsky谱系
0型语言, 0 型文 法生成的语言
1型语言 (上下文有关语言 ),如果 L-{ε}可由 1型文法
生成,则称 L 是 1型语言
2型语言 (上下文无关语言 ), 2 型文法生成的语言
3型语言 (正则语言 ),3 型文法生成的语言
如 {1x00 | x?{0,1}*} 是正则语言 (例 1)
{anbn | n>0} 是上下文无关语言 (例 2,3)
{ | i ?1} 是 0 型语言 (例 4)
定理 0型语言 ?1型语言 ?2型语言 ?3型语言
ia2
21
描述算术表达式的文法
G={{E,T,F},{a,+.-.*,/,(,)},E,P}
其中 E:算术表达式,T:项,
F:因子,a:数或变量
P,E → E+T | E-T | T
T → T*F | T/F | F
F → (E) | a
这是上下文无关文法
22
左、右线性文法的等价性
定理 设 G是右 (左 )线性文法,则存在左 (右 )线
性文法 G? 使得 L(G? )=L(G),
证明, G?用模拟 G
G= <V,T,S,P > G?= <V∪ {S?},T,S?,P?>
P,A→ αB P?,B→ Aα
A→ α S?→ Aα
S→ ε
23
一个实例 —— 模拟例 2中的 G2
可删去 G2?中的 S,这实际上就是 G3
G2= <V,T,S,P > G2? = <V ?,T ?,S ?,P ?>
V={A,B,S} V? ={A,B,S,S?}
T={0,1} T? ={0,1}
P,S→1 A P?,A→ S1
A→0 A A→ A0
A→1 A A→ A1
A→0 B B→ A0
B→0 S?→ B0
S→ ε
形式语言和
自动机初步
2
第 11章 形式语言和自动机初步
? 11.1 形式语言和形式文法
? 11.2 有穷自动机
? 11.3 有穷自动机和正则文法的等价性
? 11.4 图灵机
3
? 字符串和形式语言
? 形式文法
? 形式文法的分类
? 0型文法
? 1型文法 或上下文有关文法
? 2型文法 或上下文无关文法
? 3型文法 或正则文法
11.1 形式语言与形式文法
4
语言的基本要素
汉语
字符,汉字和标点符号
字符集,合法字符的全体
句子,一串汉字和标点符号
语法,形成句子的规则
形式语言
字符
字母表
字符串
形式文法
5
字符串
字母表 Σ,非空的有穷集合
字符串, Σ中符号的有穷序列
如 Σ ={a,b}
a,b,aab,babb
字符串 ω的 长度 |ω|,ω中的字符个数
如 |a|=1,|aab|=3
空字符串 ε,长度为 0,即不含任何符号的字符串
an, n个 a组成的字符串
Σ*,Σ上字符串的全体
6
子字符串 (子串 ),
字符串中若干连续符号组成的字符串
前缀, 最左端的子串
后缀, 最右端的子串
例如 ω =abbaab
a,ab,abb是 ω的前缀
aab,ab,b是 ω的后缀
ba是 ω的子串,但既不是前缀,也不是后缀
ω本身也是 ω的子串,且既是前缀,也是后缀
ε也是 ω的子串,且既是前缀,也是后缀
7
字符串的连接运算
设 α=a1a2 … an,β= b1b2 … bm,
αβ=a1a2 … anb1b2 … bm称作 α与 β作的 连接
如 α=ab,β=baa,αβ=abbaa,βα=baaab
对任意的字符串 α,β,γ
(1) (αβ)γ=α(βγ)
即,连接运算满足结合律
(2) εα=αε=α
即,空串 ε是连接运算的单位元
n个 α的连接记作 αn
如 (ab)3= ababab,α0=ε
8
形式语言
定义, Σ*的子集称作字母表 Σ上的 形式语言,
简称 语言
例如 Σ={a,b}
A={a,b,aa,bb}
B={an | n∈ N}
C={anbm | n,m≥1}
D={ε}
空语言 ?
9
形式文法
一个例子 —— 标识符
<标识符 >, <字母 > | <下划线 > | <标识符 > <字母 > |
<标识符 > <下划线 >| <标识符 ><数字 >
<字母 >, a | b | … | z | A | B | … | Z
<下划线 >, _
<数字 >, 0 | 1 | … | 9
10
形式文法的定义
定义 形式文法 是一个有序 4元组 G=<V,T,S,P >,
其中
(1) V是非空有穷集合,V 的元素称作 变元 或 非终极符
(2) T是非空有穷集合且 V∩T =?,T 的元素称作 终极符
(3) S∈ V 称作 起始符
(4) P是非空有穷集合,P的元素称作 产生式 或 改写规则,
形如 α→ β,其中 α,β∈ (V∪ T)*且 α≠ε,
11
文法生成的语言
设文法 G = <V,T,S,P>,ω,λ∈ (V∪ T)*,
ω ?λ,存在 α→ β∈ P和 ξ,η∈ (V∪ T)*,使得
ω= ξαη,λ= ξβη
称 ω直接派生 出 λ,
ω λ,存在 ω1,ω2,…,ωm,使得
ω= ω1 ? ω2 ? … ? ωm= λ
称 ω派生 出 λ,
恒有 ω ω (当 m=1时 )
是 ? 的自反传递闭包
*
*
*
12
文法生成的语言
定义 设文法 G= <V,T,S,P >,G生成的语言
L(G)={ω∈ T* ∣ S ω}
L(G)由所有满足下述条件的字符串组成,
(1) 仅含终结符 ;
(2) 可由起始符派生出来,
定义 如果 L(G1)= L(G2),则称文法 G1与 G2等价,
*
13
举例
例 1 文法 G1= <V,T,S,P>,其中 V={S},T={a,b},
P,S→aSb | ab
L(G1)={anbn | n>0}
例 2 文法 G2= <V,T,S,P>,其中 V={A,B,S},T={0,1},
P,S→1 A,A→0 A | 1A | 0B,B→0
L(G2)={1x00 | x?{0,1}*}
例 3 文法 G3= <V,T,S,P>,其中 V={A,B,S},T={0,1},
P,S→B 0,B→A 0,A→A 1 | A0,A→1
L(G3)= L(G2),G3与 G2等价
14
例 4 G= <V,T,S,P>,其中 V={S,A,B,C,D,E},T={a},
P,(1) S→ACaB (2) Ca→aaC (3) CB→DB
(4) CB→E (5) aD→Da (6) AD→AC
(7) aE→Ea (8) AE→ ε
试证明, ?i ?1,S
证, a2 和 a4 的派生过程
S ? ACaB (1)
? AaaCB (2)
? AaaE (4)
? AEaa 2次 (7)
a2 (8) *
ia2
*
举例 (续 )
15
例 4 (续 )
S AaaCB
? AaaDB (3)
ADaaB 2次 (5)
? ACaaB (6)
AaaaaCB 2次 (2)
? AaaaaE (4)
AEaaaa 4次 (7)
? a4 (8)
*
*
*
*
16
例 4(续 )
先用归纳法证明 ?i ?1,
当 i=1 时结论成立,假设对 i 结论成立,
(3)
2i 次 (5)
(6)
2i 次 (2)
得证对 i +1 结论成立,故对所有的 i 成立,
CBAa i2
*
S
*
CBAa i2
DBAa i2
BA D a i2
BACa i2
CBAa i 12 ?
*
*
S
17
例 4 (续 )
于是,?i ?1,
(4)
2i 次 (7)
(8)
可以证明,
L(G) = { | i ?1} ia2
*
CBAa i2
EAa i2
iAEa 2
ia2
*
S
18
形式文法的分类
— Chomsky谱系
0型文法 (短语结构文法,无限制文法 )
1型文法 (上下文有关文法 ),
所有产生式 α→ β,满足 |α|?|β|
另一个等价的定义, 所有的产生式形如
ξAη→ ξαη
其中 A?V,ξ,η,α?(V∪ T)*,且 α?ε
2型文法 (上下文无关文法 ),
所有的产生式形如 A→ α
其中 A?V,α?(V∪ T)*,
19
形式文法的分类 (续 )
3型文法 (正则文法 ),右线性文法和左线性文法的统称
右线性文法, 所有的产生式形如
A→ αB 或 A→ α
左线性文法, 所有的产生式形如
A→ Bα 或 A→ α
其中 A,B?V,α?T*
例 1是上下文无关文法
例 2是右线性文法,例 3是左线性文法,都是正则文法
例 4是 0型文法
20
Chomsky谱系
0型语言, 0 型文 法生成的语言
1型语言 (上下文有关语言 ),如果 L-{ε}可由 1型文法
生成,则称 L 是 1型语言
2型语言 (上下文无关语言 ), 2 型文法生成的语言
3型语言 (正则语言 ),3 型文法生成的语言
如 {1x00 | x?{0,1}*} 是正则语言 (例 1)
{anbn | n>0} 是上下文无关语言 (例 2,3)
{ | i ?1} 是 0 型语言 (例 4)
定理 0型语言 ?1型语言 ?2型语言 ?3型语言
ia2
21
描述算术表达式的文法
G={{E,T,F},{a,+.-.*,/,(,)},E,P}
其中 E:算术表达式,T:项,
F:因子,a:数或变量
P,E → E+T | E-T | T
T → T*F | T/F | F
F → (E) | a
这是上下文无关文法
22
左、右线性文法的等价性
定理 设 G是右 (左 )线性文法,则存在左 (右 )线
性文法 G? 使得 L(G? )=L(G),
证明, G?用模拟 G
G= <V,T,S,P > G?= <V∪ {S?},T,S?,P?>
P,A→ αB P?,B→ Aα
A→ α S?→ Aα
S→ ε
23
一个实例 —— 模拟例 2中的 G2
可删去 G2?中的 S,这实际上就是 G3
G2= <V,T,S,P > G2? = <V ?,T ?,S ?,P ?>
V={A,B,S} V? ={A,B,S,S?}
T={0,1} T? ={0,1}
P,S→1 A P?,A→ S1
A→0 A A→ A0
A→1 A A→ A1
A→0 B B→ A0
B→0 S?→ B0
S→ ε
