- 构造自动机：DFA、NFA、ε-NFA、PDA、DPDA、TM
- 设计正则表达式/正则文法、上下文无关文法
- 泵引理+封闭性证明不是正则语言
- 等价性转换
- NFA和DFA
- FA和正则表达式
- PDA和CFG
- CNF和GNF
- 语言的接受和设计
确定的有穷自动机(DFA, Deterministic Finite Automaton) A 为五元组
A
=
(
Q
,
Σ
,
δ
,
q
0
,
F
)
A = (Q, Σ, δ, q0, F)
A=(Q,Σ,δ,q0,F)
例：请设计 DFA, 在任何由 0 和 1 构成的串中, 接受含有 01 子串的全部串.
- 未发现 01, 即使 0 都还没出现过;
- 未发现 01, 但刚刚读入字符是 0;
- 已经发现了 01
因此 DFA A 的可定义为:
A
=
(
{
q
1
,
q
2
,
q
3
}
,
{
0
,
1
}
,
δ
,
q
1
,
{
q
3
}
)
A\ = \ (\{ q1,\ q2,\ q3\},\ \{ 0,\ 1\},\ \delta,\ q1,\ \{ q3\})
A = ({q1, q2, q3}, {0, 1}, δ, q1, {q3})
其中 δ 为:
δ
(
q
1
,
1
)
=
q
1
δ(q1, 1) = q1
δ(q1,1)=q1
δ
(
q
2
,
1
)
=
q
3
δ(q2, 1) = q3
δ(q2,1)=q3
δ
(
q
3
,
1
)
=
q
3
δ(q3, 1) = q3
δ(q3,1)=q3
δ
(
q
1
,
0
)
=
q
2
δ(q1, 0) = q2
δ(q1,0)=q2
δ
(
q
2
,
0
)
=
q
2
δ(q2, 0) = q2
δ(q2,0)=q2
δ
(
q
3
,
0
)
=
q
3
δ(q3, 0) = q3
δ(q3,0)=q3
状态转移图
状态转移表
非确定有穷自动机(NFA, Nondeterministic Finite Automaton) A 为五元组
A
=
(
Q
,
Σ
,
δ
,
q
0
,
F
)
A = (Q, Σ, δ, q0, F)
A=(Q,Σ,δ,q0,F)
与DFA区别
- δ δ δ : Q × Σ = 2 Q Q \times \Sigma = 2^{Q} Q×Σ=2Q
- 转移后为一个状态集合
- 同一个状态在相同的输入下，可以有多个转移状态
- 自动机可以处在多个当前状态
例：接受全部以 01 结尾的串的 NFA.
解：五元组为
A
=
(
{
q
0
,
q
1
,
q
2
}
,
{
0
,
1
}
,
δ
,
q
0
,
{
q
2
}
)
A\ = \ (\{ q0,\ q1,\ q2\},\ \{ 0,\ 1\},\ \delta,\ q0,\ \{ q2\})
A = ({q0, q1, q2}, {0, 1}, δ, q0, {q2})
转移函数 δ:
DFA、NFA和ε-NFA性质：
ε-NFA与NFA
例：语言 L = w ∈ 0 , 1 ∗ ∣ w 倒 数 3 个 字 符 至 少 有 一 个 是 1 L = {w ∈ {0, 1}∗ | w 倒数 3 个字符至少有一个是 1} L=w∈0,1∗∣w倒数3个字符至少有一个是1 的ε-NFA.
此后, 不再明确区分 ε-NFA 和 NFA, 而认为它们都是 NFA.
ε
−
闭
包
：
q
0
→
所
有
q
0
能
到
达
的
状
态
的
集
合
ε-闭包： {q_0} → {所有q_0能到达的状态的集合}
ε−闭包：q0→所有q0能到达的状态的集合
记为
E
c
l
o
s
e
(
q
)
Eclose(q)
Eclose(q)
例：求以下状态的 ε − c l o s u r e ε - closure ε−closure
解：
- E ( 1 ) = { 1 , 2 , 4 , 3 , 6 } E(1) = \{ 1, 2, 4, 3, 6 \} E(1)={1,2,4,3,6}
- E ( 2 ) = { 2 , 3 , 6 } E(2) = \{ 2, 3, 6 \} E(2)={2,3,6}
- E ( 3 ) = { 3 , 6 } E(3) = \{ 3, 6 \} E(3)={3,6}
- E ( 4 ) = { 4 } E(4) = \{ 4 \} E(4)={4}
- E ( 5 ) = { 5 , 7 } E(5) = \{ 5, 7 \} E(5)={5,7}
- E ( 6 ) = { 6 } E(6) = \{ 6 \} E(6)={6}
- E ( 7 ) = { 7 } E(7) = \{ 7 \} E(7)={7}
扩展转移函数
例：将以下NFA转换为DFA
解：
| 0 0 0 | 1 1 1 | |
|---|---|---|
| { q 0 } \{q_0\} {q0} | { q 0 } \{q_0\} {q0} | { q 0 , q 1 , q 2 , q 3 } \{q_0, q_1,q_2, q_3\} {q0,q1,q2,q3} |
| 0 0 0 | 1 1 1 | |
|---|---|---|
| { q 0 } \{q_0\} {q0} | { q 0 } \{q_0\} {q0} | { q 0 , q 1 , q 2 , q 3 } \{q_0, q_1, q_2, q_3\} {q0,q1,q2,q3} |
| { q 0 , q 1 , q 2 , q 3 } \{q_0, q_1,q_2, q_3\} {q0,q1,q2,q3} | { q 0 , q 2 , q 3 } \{q_0, q_2, q_3\} {q0,q2,q3} | { q 0 , q 1 , q 2 , q 3 } \{q_0, q_1, q_2, q_3\} {q0,q1,q2,q3} |
| 0 0 0 | 1 1 1 | |
|---|---|---|
| { q 0 } \{q_0\} {q0} | { q 0 } \{q_0\} {q0} | { q 0 , q 1 , q 2 , q 3 } \{q_0, q_1, q_2, q_3\} {q0,q1,q2,q3} |
| { q 0 , q 1 , q 2 , q 3 } \{q_0, q_1,q_2, q_3\} {q0,q1,q2,q3} | { q 0 , q 2 , q 3 } \{q_0, q_2, q_3\} {q0,q2,q3} | { q 0 , q 1 , q 2 , q 3 } \{q_0, q_1, q_2, q_3\} {q0,q1,q2,q3} |
| { q 0 , q 2 , q 3 } \{q_0, q_2, q_3\} {q0,q2,q3} | { q 0 , q 3 } \{q_0, q_3\} {q0,q3} | { q 0 , q 1 , q 2 , q 3 } \{q_0, q_1, q_2, q_3\} {q0,q1,q2,q3} |
| 0 0 0 | 1 1 1 | |
|---|---|---|
| { q 0 } \{q_0\} {q0} | { q 0 } \{q_0\} {q0} | { q 0 , q 1 , q 2 , q 3 } \{q_0, q_1, q_2, q_3\} {q0,q1,q2,q3} |
| { q 0 , q 1 , q 2 , q 3 } \{q_0, q_1,q_2, q_3\} {q0,q1,q2,q3} | { q 0 , q 2 , q 3 } \{q_0, q_2, q_3\} {q0,q2,q3} | { q 0 , q 1 , q 2 , q 3 } \{q_0, q_1, q_2, q_3\} {q0,q1,q2,q3} |
| { q 0 , q 2 , q 3 } \{q_0, q_2, q_3\} {q0,q2,q3} | { q 0 , q 3 } \{q_0, q_3\} {q0,q3} | { q 0 , q 1 , q 2 , q 3 } \{q_0, q_1, q_2, q_3\} {q0,q1,q2,q3} |
| { q 0 , q 3 } \{q_0, q_3\} {q0,q3} | { q 0 } \{q_0\} {q0} | { q 0 , q 1 , q 2 , q 3 } \{q_0, q_1, q_2, q_3\} {q0,q1,q2,q3} |
| 0 0 0 | 1 1 1 | |
|---|---|---|
| → { q 0 } →\{q_0\} →{q0} | { q 0 } \{q_0\} {q0} | { q 0 , q 1 , q 2 , q 3 } \{q_0, q_1, q_2, q_3\} {q0,q1,q2,q3} |
| ∗ { q 0 , q 1 , q 2 , q 3 } * \{q_0, q_1,q_2, q_3\} ∗{q0,q1,q2,q3} | { q 0 , q 2 , q 3 } \{q_0, q_2, q_3\} {q0,q2,q3} | { q 0 , q 1 , q 2 , q 3 } \{q_0, q_1, q_2, q_3\} {q0,q1,q2,q3} |
| ∗ { q 0 , q 2 , q 3 } * \{q_0, q_2, q_3\} ∗{q0,q2,q3} | { q 0 , q 3 } \{q_0, q_3\} {q0,q3} | { q 0 , q 1 , q 2 , q 3 } \{q_0, q_1, q_2, q_3\} {q0,q1,q2,q3} |
| ∗ { q 0 , q 3 } * \{q_0, q_3\} ∗{q0,q3} | { q 0 } \{q_0\} {q0} | { q 0 , q 1 , q 2 , q 3 } \{q_0, q_1, q_2, q_3\} {q0,q1,q2,q3} |
对于任意两个状态，一定是
- 等价
- 可区分
二者之一
等价
可区分
例：化简以下DFA
- 直接标记终态和非终态之间的状态对
- 标记所有经过字符 0 到达终态和非终态的状态对
- {D, F }×{A, B, C, E, G, H}- 标记所有经过字符 1 到达终态和非终态的状态对
- {B, H }×{A, C, D, E, F, G}- 此时还有 [A,E], [A,G], [B,H], [D,F], [E,G] 未标记, 只需逐个检查.
- [A,G] 是可区分的, 因为经串 01 到可区分的 [C,E];
- [E,G] 是可区分的, 因为经串 10 到可区分的 [C,H].- [A,E], [B,H] 和 [D,F] 在经过很短的字符串后, 都会到达相同状态，因此都是等价的.
语言是字符串集合。
语言的运算：并、连接、幂、克林闭包
递归定义：
如果E为字母表，则2上的正则表达式递归定义为:
- 0是一个正则表达式，表示空语言;
- ε ε ε是一个正则表达式，表示语言{e};
- 任意 a ∈ E a∈E a∈E，a是一个正则表达式，表示语言{a};
- 如果正则表达式 r 和 s 分别表示语言 R R R和 S S S，那么 r + s ， r s , r ∗ 和 ( r ) r+s，rs, r^*和 ( r ) r+s，rs,r∗和(r)都是正则表达式
- 分别表示语言 R ∪ S ， R ⋅ S ， R ∗ 和 R R∪S，R·S，R*和R R∪S，R⋅S，R∗和R
优先级：括号>星（*）>连接（×）>加（+）
例：L = {w | w ∈ {0, 1}∗ and w has no pair of consecutive 0’s.}
正则表达式到自动机的转换分为以下4种
例：正则表达式 ( 0 + 1 ) ∗ 1 ( 0 + 1 ) (0+1)^*1(0+1) (0+1)∗1(0+1)转换为 ε − N F A ε-NFA ε−NFA
例：
0
+
1
0+1
0+1
例： ( 0 + 1 ) ∗ (0+1)^* (0+1)∗
若干例题
2.
3.
R i j ( k ) : 0 < = k < = n R_{ij}^{(k)}: 0<=k<=n Rij(k):0<=k<=n： i i i到 j j j路径上的正则表达式
- no inner node is greater than k
当k≥1时进行归纳法
公式：
例：
解：
即：前 N N N的字符中存在一段可以在该位置循环出现
泵引理只是正则语言的必要条件，只能用来证明某个语言不是正则的
证明：
例：
正则语言经某些运算后得到的新语言仍保持正则，称正则语言在这些运算下封闭
正则语言 L 和 M, 在这些运算下封闭
考点：能够运用这些性质，结合泵引理证明一个语言是否是正则语言
自动机的转换
证明思路
定义：上下文无关文法(CFG, 简称文法) G 是一个四元组 G = ( V , T , P , S ) G = (V, T, P, S) G=(V,T,P,S)
产生
符号
例：
- 回文
G = ( A , 0 , 1 , A → ε ∣ 0 ∣ 1 ∣ 0 A 0 ∣ 1 A 1 , A ) G = ({A}, {0, 1}, {A → ε | 0 | 1 | 0A0 | 1A1}, A) G=(A,0,1,A→ε∣0∣1∣0A0∣1A1,A)- L={ w∈{0,1}* | w contains same number of 0’s and 1’s }
R = ( S , 0 , 1 , P , S ) R = ({S }, {0,1}, P, S ) R=(S,0,1,P,S)
P ： S → ε ∣ 0 S 1 ∣ 1 S 0 ∣ S S P：S → ε | 0S1 | 1S0 | SS P：S→ε∣0S1∣1S0∣SS
例：用算数表达式文法 G e x p G_{exp} Gexp, 将 a ∗ ( a + b 00 ) a ∗ (a + b00) a∗(a+b00) 归约的过程
- E → I
- E → E + E
- E → E ∗ E
- E → (E)
- I → a
- I → b
- I → Ia
- I → Ib
- I → I0
- I → I1
目标：从 a ∗ ( a + b 00 ) a ∗ (a + b00) a∗(a+b00)规约到 E E E
解：
即：
- 最左派生
- 最右派生
为限制派生的随意性, 要求只替换符号串中最左边变元的派生过程, 称为最
左派生, 记为
⟹
l
m
或
⟹
lm
∗
\underset{lm}{\Longrightarrow} 或 \overset{*}{\underset{\text{lm}}{\Longrightarrow}}
lm⟹或lm⟹∗
只替换最右的, 称为最右派生, 记为
⟹
r
m
或
⟹
rm
∗
\underset{rm}{\Longrightarrow} 或 \overset{*}{\underset{\text{rm}}{\Longrightarrow}}
rm⟹或rm⟹∗
任何派生都有等价的最左派生和最右派生
当 w w w在 L ( G ) L(G) L(G)中时满足：
- w w w仅由终结符组成
- 初始符号 S S S能派生出 w w w
即：
L ( G ) = { w ∣ w ϵ T ∗ , S ⟹ G ∗ w } L\left( G \right) = \left\{ w\ |\ w\epsilon T^{*},\ S\overset{*}{\underset{G}{\Longrightarrow}}w \right\} L(G)={w ∣ wϵT∗, SG⟹∗w}
语言 L 是某个 CFG G 定义的语言, 即 L = L ( G ) L = L(G) L=L(G), 则称 L 为上下文无关语言(CFL, Context-Free Language).
CFG G = (V, T, P, S) 的语法分析树(语法树或派生树) 为:
例：
CFG G = (V, T, P, S) 且 A ∈ V , 那么文法 G 中
- A ⟹ ∗ α A\overset{*}{\Longrightarrow}\alpha A⟹∗α 当且仅当 G 中存在以 A 为根节点产物为 α 的语法树
有些文法的歧义性, 可以通过重新设计文法来消除
- 定义同样的语言可以有多个文法, 如果 CFL L 的所有文法都是歧义的，那么称语言 L 是固有歧义的
- 定义同样的语言可以有多个文法, 如果 CFL L 的所有文法都是歧义的, 那么称语言 L 是固有歧义的.
- “判定任何给定 CFG G 是否歧义”是一个不可判定问题
文法化简的可靠顺序
- 消除ε-产生式;
- 消除单元产生式;
- 消除非产生的无用符号;
- 消除非可达的无用符号.
- 初始符号在派生过程中能派生的语言，前后为若干终止符、中间的单一符号为可达的；
- 某一符号和前后的若干终止符能够最终派生为均为终止符的语言，则其是产生的；
- 可达 + 产生 = 有用
- 非（有用）= 无用 = 非（可达） 或 非（产生）
步骤：
注：先寻找并消除全部非“产生的”符号，再寻找并消除全部非“可达的”符号，否则可能消除不完整。
步骤：
例：
- 消除 CFG G = ({S, A, B}, {a, b}, P, S) 的 ε-产生式.
S → AB
A → AaA | ε
B → BbB | ε解：
- CFG G′ 为
S → AB | A | B
A → AaA | Aa | aA | a
B → BbB | Bb | bB | b
单元产生式：例如 A → B
步骤：
例：
- 消除文法的单元产生式
S → A | B | 0S1
A → 0A | 0
B → 1B | 1解：
- 单位对为 [S, A] 和 [S, B], 带入得:
S → 0S1
S → 0A | 0
S → 1B | 1
A → 0A | 0
B → 1B | 1
- 这里的 A, B 和 C 是变元, a 是终结符.
- 利用 CNF 派生长度为 n 的串, 刚好需要 2n − 1 步
方法：
例：
- CFG G = ( S , A , B , a , b , P , S ) G = ({S, A, B}, {a, b}, P, S) G=(S,A,B,a,b,P,S), 产生式集合 P 为:
S → b A ∣ a B S → bA | aB S→bA∣aB
A → b A A ∣ a S ∣ a A → bAA | aS | a A→bAA∣aS∣a
B → a B B ∣ b S ∣ b B → aBB | bS | b B→aBB∣bS∣b- 请设计等价的 CNF 文法.
解:
- CNF 为：
S → C b A ∣ C a B S → CbA | CaB S→CbA∣CaB
A → C a S ∣ C b D 1 ∣ a A → C_aS | C_bD_1 | a A→CaS∣CbD1∣a
D 1 → A A D1 → AA D1→AA
C a → a C_a → a Ca→a
B → C b S ∣ C a D 2 ∣ b B → C_bS | C_aD_2 | b B→CbS∣CaD2∣b
D 2 → B B D2 → BB D2→BB
C b → b C_b → b Cb→b
- GNF 每个产生式都会引入一个终结符
- 长度为 n 的串的派生恰好是 n 步
例：
解:
特殊情况：
- 直接左递归
- 间接左递归
下推自动机(PDA, Pushdown Automata) P 为七元组
P
=
(
Q
,
Σ
,
Γ
,
δ
,
q
0
,
Z
0
,
F
)
P = (Q, Σ, Γ, δ, q_0, Z_0, F)
P=(Q,Σ,Γ,δ,q0,Z0,F)
例：设计识别 L 01 = { 0 n 1 n ∣ n ≥ 1 } L_{01} = \{0^n1^n | n ≥ 1\} L01={0n1n∣n≥1} 的 PDA
例：设计识别 L w w r = { w w R ∣ w ∈ ( 0 + 1 ) ∗ } L_{ww^r} = \{ww^R | w ∈ (0 + 1)^∗\} Lwwr={wwR∣w∈(0+1)∗} 的 PDA
为描述 PDA 瞬间的格局, 定义
Q
×
Σ
∗
×
Γ
∗
Q × Σ^∗ × Γ^∗
Q×Σ∗×Γ∗ 中三元组
(
q
,
w
,
γ
)
(q, w, γ)
(q,w,γ)
为瞬时描述(ID, Instantaneous Description), 表示此时 PDA 处于状态
q
q
q, 剩
余输入串
w
w
w, 栈为
γ
γ
γ.
在 PDA
P
P
P 中如果
(
p
,
β
)
∈
δ
(
q
,
a
,
Z
)
(p, β) ∈ δ(q, a, Z)
(p,β)∈δ(q,a,Z), 由
(
q
,
a
w
,
Z
α
)
(q, aw, Zα)
(q,aw,Zα) 到
(
p
,
w
,
β
α
)
(p, w, βα)
(p,w,βα) 的变化, 称为瞬时描述（ID）的转移
⊢
P
⊢_P
⊢P, 记为
(
q
,
a
w
,
Z
α
)
⊢
P
(
p
,
w
,
β
α
)
(q, aw, Zα) ⊢_P (p, w, βα)
(q,aw,Zα)⊢P(p,w,βα)
其中
w
∈
Σ
∗
,
α
∈
Γ
∗
w ∈ Σ^∗, α ∈ Γ^∗
w∈Σ∗,α∈Γ∗.
若有瞬时描述（ID）
I
I
I,
J
J
J 和
K
K
K, 递归定义
⊢
P
∗
⊢^*_P
⊢P∗ 为:
若 P P P 已知, 可省略, 记为 ⊢ ⊢ ⊢ 和 ⊢ ∗ ⊢^* ⊢∗ .
例：语言 L 01 = { 0 n 1 n ∣ n ≥ 1 } L_{01} = \{0^n1^n | n ≥ 1\} L01={0n1n∣n≥1} 的 PDA, 识别 0011 时的 ID 序列.
解：
( q 0 , 0011 , Z 0 ) ⊢ ( q 0 , 011 , 0 Z 0 ) ⊢ ( q 0 , 11 , 00 Z 0 ) ⊢ ( q 1 , 1 , 0 Z 0 ) ⊢ ( q 1 , ε , Z 0 ) ⊢ ( q 2 , ε , Z 0 ) (q_0, 0011, Z_0) ⊢ (q_0, 011, 0Z_0) ⊢ (q_0, 11, 00Z_0) ⊢ (q_1, 1, 0Z_0) ⊢ (q_1, ε, Z_0) ⊢ (q_2, ε, Z_0) (q0,0011,Z0)⊢(q0,011,0Z0)⊢(q0,11,00Z0)⊢(q1,1,0Z0)⊢(q1,ε,Z0)⊢(q2,ε,Z0)
定理：
对
∀
w
∈
Σ
∗
,
∀
γ
∈
Γ
∗
∀w ∈ Σ^∗, ∀γ ∈ Γ^∗
∀w∈Σ∗,∀γ∈Γ∗, 如果
(
q
,
x
,
α
)
⊢
P
∗
(
p
,
y
,
β
)
,
(q, x, α) ⊢^*_P (p, y, β),
(q,x,α)⊢P∗(p,y,β),
那么
(
q
,
x
w
,
α
γ
)
⊢
P
∗
(
p
,
y
w
,
β
γ
)
(q, xw, αγ) ⊢^*_P (p, yw, βγ)
(q,xw,αγ)⊢P∗(p,yw,βγ)
即：在可以转移的两个瞬时描述的剩余输入串后加入相同的剩余输入串、栈后加入相同的栈，仍然可以转移；
对
∀
w
∈
Σ
∗
∀w ∈ Σ^∗
∀w∈Σ∗, 如果
(
q
,
x
w
,
α
)
⊢
P
∗
(
p
,
y
w
,
β
)
,
(q, xw, α) ⊢^*_P (p, yw, β),
(q,xw,α)⊢P∗(p,yw,β),
那么
(
q
,
x
,
α
)
⊢
P
∗
(
p
,
y
,
β
)
(q, x, α) ⊢^*_P (p, y, β)
(q,x,α)⊢P∗(p,y,β)
即：在可以转移的两个瞬时描述的剩余输入串后删除相同的输入串，仍然可以转移；
PDA P = ( Q , Σ , Γ , δ , q 0 , Z 0 , F ) P = (Q, Σ, Γ, δ, q_0, Z_0, F) P=(Q,Σ,Γ,δ,q0,Z0,F), 以两种方式接受语言:
- P 以终态方式接受的语言, 记为 L ( P ) L(P) L(P), 定义为 L ( P ) = w ∣ ( q 0 , w , Z 0 ) ⊢ ∗ ( p , ε , γ ) , p ∈ F . L(P) = {w | (q_0, w, Z_0) ⊢^*(p, ε, γ), p ∈ F}. L(P)=w∣(q0,w,Z0)⊢∗(p,ε,γ),p∈F.
- P 以空栈方式接受的语言, 记为 N ( P ) N(P) N(P), 定义为 N ( P ) = w ∣ ( q 0 , w , Z 0 ) ⊢ ∗ ( p , ε , ε ) . N(P) = {w | (q_0, w, Z_0) ⊢^*(p, ε, ε)}. N(P)=w∣(q0,w,Z0)⊢∗(p,ε,ε).
定理及证明（构造）方法：
例1：识别 L w w r L_{ww^r} Lwwr 的 PDA P P P , 从终态方式接受, 改为空栈方式接受.
例2：接受 L = { w ∈ { 0 , 1 } ∗ ∣ w 中 字 符 0 和 1 的 数 量 相 同 } L = \{w ∈ \{0, 1\}^∗ | w 中字符 0 和 1 的数量相同\} L={w∈{0,1}∗∣w中字符0和1的数量相同} 的 PDA
例3：接受 L = { 0 n 1 m ∣ 0 ≤ n ≤ m ≤ 2 n } L = \{0^n1^m | 0 ≤ n ≤ m ≤ 2n\} L={0n1m∣0≤n≤m≤2n} 的 PDA
例：设计语言 L = { 0 n 1 m ∣ 1 ≤ m ≤ n } L = \{0^n1^m | 1 ≤ m ≤ n\} L={0n1m∣1≤m≤n} 的 PDA，并转换为CFG
解：
- PDA：
CFG G:
S
→
A
B
S → AB
S→AB
A
→
0
A
∣
ε
A → 0A | ε
A→0A∣ε
B
→
0
B
1
∣
01
B → 0B1 | 01
B→0B1∣01
字符串 00011 的最左派生:
S
⟹
l
m
A
B
⟹
l
m
0
A
B
⟹
l
m
0
B
⟹
l
m
00
B
1
⟹
l
m
00011
S \underset{lm}{\Longrightarrow} AB \underset{lm}{\Longrightarrow} 0AB \underset{lm}{\Longrightarrow} 0B \underset{lm}{\Longrightarrow} 00B1 \underset{lm}{\Longrightarrow} 00011
Slm⟹ABlm⟹0ABlm⟹0Blm⟹00B1lm⟹00011
用 PDA 栈顶符号的替换, 模拟文法的最左派生
- 栈顶为变元：输入 ε ε ε，变元派生（如： ε , S → 0 S 1 ε, S → 0S1 ε,S→0S1）
- 栈顶为终结符：输入非空字符，输入串减少，栈顶弹出
如果 PDA
P
=
(
Q
,
Σ
,
Γ
,
δ
,
q
0
,
Z
0
,
∅
)
P = (Q, Σ, Γ, δ, q_0, Z_0, ∅)
P=(Q,Σ,Γ,δ,q0,Z0,∅), 那么构造 CFG
G
=
(
V
,
Σ
,
P
′
,
S
)
G = (V, Σ, P^′, S)
G=(V,Σ,P′,S), 其中
V
V
V 和
P
′
P^′
P′ 为
简单记忆
例：将 PDA P = ({p, q}, (0, 1), {X, Z}, δ, q, Z) 转为 CFG, 其中 δ 如下：
解：
化简：
如果 GNF 格式的 CFG
G
=
(
V
,
T
,
P
′
,
S
)
G = (V, T, P^′, S)
G=(V,T,P′,S), 那么构造 PDA
P
=
(
{
q
}
,
T
,
V
,
δ
,
q
,
S
,
∅
)
P = (\{q\}, T, V, δ, q, S, ∅)
P=({q},T,V,δ,q,S,∅)
为每个产生式, 定义 δ 为:
δ
(
q
,
a
,
A
)
=
{
(
q
,
β
)
∣
A
→
a
β
∈
P
′
}
δ(q, a, A) = \{(q, β) | A → aβ ∈ P^′\}
δ(q,a,A)={(q,β)∣A→aβ∈P′}
即：每次读入终结符，将栈中变元进行派生（弹栈+压栈），直到栈中均为终结符。
例：文法 S → a A A , A → a S ∣ b S ∣ a S → aAA, A → aS | bS | a S→aAA,A→aS∣bS∣a 为 GNF 格式, 构造等价的 PDA
如果 PDA P = ( Q , Σ , Γ , δ , q 0 , Z 0 , F ) P = (Q, Σ, Γ, δ, q_0, Z_0, F) P=(Q,Σ,Γ,δ,q0,Z0,F) 满足
∀ ( q , a , Z ) ∈ Q × Σ × Γ ∀(q, a, Z) ∈ Q × Σ × Γ ∀(q,a,Z)∈Q×Σ×Γ 满足 ∣ δ ( q , a , Z ) ∣ + ∣ δ ( q , ε , Z ) ∣ ≤ 1 |δ(q, a, Z)| + |δ(q, ε, Z)| ≤ 1 ∣δ(q,a,Z)∣+∣δ(q,ε,Z)∣≤1
即：每一个瞬时描述下至多有一个转移状态（可以无动作）
则称 P P P 为确定型下推自动机（DPDA）
DPDA P P P 以终态方式接受的语言 L ( P ) L(P) L(P) 称为确定性上下文无关语言（DCFL）
注：DPDA 与 PDA 不等价
例：任何 DPDA 都无法接受 L w w r L_{ww^r} Lwwr, 但是可以接受
L w c w r = { w c w R ∣ w ∈ ( 0 + 1 ) ∗ } L_{wcw^r} = \{wcw^R | w ∈ (0 + 1)^∗\} Lwcwr={wcwR∣w∈(0+1)∗}
设计DPDA
DCFL 的重要应用
- 非固有歧义语言的真子集
- 程序设计语言的语法分析器
- LR(k) 文法, Yacc 的基础, 解析时间复杂度为 O(n)
- 前缀性质：如果语言 L 中不存在字符串 x 和 y, 使 x 是 y 的前缀, 称语言 L 满足前缀性质.
- DPDA P P P 且 L = N ( P ) L = N(P) L=N(P), 当且仅当 L L L 有前缀性质, 且存在 DPDA P ′ P^′ P′ 使 L = L ( P ′ ) L = L(P ′) L=L(P′).
- DPDA P P P 的 N ( P ) N(P) N(P) 更有限, 即使正则语言 0 ∗ 0^∗ 0∗ 也无法接受
- 但却可以被某个 DPDA 以终态方式接受
DPDA 与歧义文法
DPDA P P P, 语言 L = L ( P ) L = L(P) L=L(P), 那么 L L L 有无歧义的 CFG
如果语言
L
L
L 是 CFL, 那么存在正整数
N
N
N, 对
∀
z
∈
L
∀z ∈ L
∀z∈L,
只要
∣
z
∣
≥
N
|z| ≥ N
∣z∣≥N, 就可以将
z
z
z 分为五部分
z
=
u
v
w
x
y
z = uvwxy
z=uvwxy 满足:
例：证明 L = { 0 n 1 n 2 n ∣ n ≥ 1 } L = \{0^{n}1^{n}2^{n} | n ≥ 1\} L={0n1n2n∣n≥1} 不是上下文无关语言
解：
例：证明 L = { w w ∣ w ∈ 0 , 1 ∗ } L = \{ww | w ∈ {0, 1}^∗\} L={ww∣w∈0,1∗} 不是上下文无关的
(错误的) 证明: 假设
L
L
L 是 CFL. 取
z
=
0
N
1
0
N
1
z = 0^N10^N1
z=0N10N1, 那么
z
=
u
v
w
x
y
z = uvwxy
z=uvwxy 为
则对任意
i
≥
0
i ≥ 0
i≥0, 有
u
v
i
w
x
i
y
∈
L
uv^iwx^iy ∈ L
uviwxiy∈L, 满足泵引理.
(正确的) 证明: 假设 L L L 是 CFL. 取 z = 0 N 1 N 0 N 1 N z = 0^N1^N0^N1^N z=0N1N0N1N, 将 z z z 分为 z = u v w x y z = uvwxy z=uvwxy 时
封闭
不封闭
- 交
- 补运算
两个字母表
Σ
\Sigma
Σ 到
Γ
\Gamma
Γ 的函数
s
:
Σ
→
2
Γ
∗
s\ :\ \Sigma\ \rightarrow 2^{\Gamma^{*}}
s : Σ →2Γ∗ 称为代换.
Σ
\Sigma
Σ 中的一个字符
a
a
a 在
s
s
s 的作用下为
Γ
\Gamma
Γ 上的一个语言
L
a
L_{a}
La, 即
s ( a ) = L a s(a)\ = \ La s(a) = La
扩展 s s s 的定义到字符串,
s ( ε ) = ε s(\varepsilon)\ = \ \varepsilon s(ε) = ε
s ( x a ) = s ( x ) s ( a ) s(xa)\ = \ s(x)s(a) s(xa) = s(x)s(a)
再扩展 h h h 到语言, 对 ∀ L ⊆ Σ ∗ \forall\text{L\ } \subseteq \ \Sigma^{*} ∀L ⊆ Σ∗
s ( L ) = ⋃ x ∈ L s ( x ) s(L)\ = \ \bigcup_{x \in L}^{}{s(x)} s(L) = x∈L⋃s(x)
定理：如果有 Σ Σ Σ 上的 CFL L L L 和代换 s s s, 且每个 a ∈ Σ a ∈ Σ a∈Σ 的 s ( a ) s(a) s(a) 都是 CFL, 那么 s ( L ) s(L) s(L) 也是 CFL
即：可以把CFL的每个终结符扩展为一个CFL，生成的语言还是CFL
具体构造方法：
设 CFL L L L 的文法 G = ( V , T , P , S ) G\ = \ (V,\ T,\ P,\ S) G = (V, T, P, S), 每个 s ( a ) s(a) s(a) 的文法 G a = ( V a , T a , P a , S a ) G_{a} = \ (V_{a},\ T_{a},\ P_{a},\ S_{a}) Ga= (Va, Ta, Pa, Sa).
那么 s ( L ) s(L) s(L) 的文法可以构造为
G ′ = ( V ′ , T ′ , P ′ , S ) G'\ = \ (V\ ',\ T\ ',\ P\ ',\ S)\ G′ = (V ′, T ′, P ′, S)
V ′ = V ∪ ( ⋃ a ∈ T V a ) V^{'}=V \cup (\bigcup_{a \in T}^{}V_{a}\ ) V′=V∪(⋃a∈TVa )
T ′ = ⋃ a ∈ T T a T^{'}=\bigcup_{a \in T}^{}T_{a} T′=⋃a∈TTa
P ′ P^{'} P′包括每个 P a P_{a} Pa 和 P P P 中产生式，但是要将 P P P的产生式中每个终结符 a a a均替换为文法 G a G_{a} Ga 的开始符号 S a S_{a} Sa.
例： 请证明语言 L L L 不是 CFL L = { w ∈ { a , b , c } ∗ ∣ n a ( w ) = n b ( w ) = n c ( w ) } L = \{w ∈ {\{a, b, c\}}^∗ | n_a(w) = n_b(w) = n_c(w)\} L={w∈{a,b,c}∗∣na(w)=nb(w)=nc(w)}，其中 n a ( w ) n_a(w) na(w) 表示 w w w 中 a a a 的个数.
证明:
空性: 只需判断文法的开始符号 S 是否为非产生的
有穷性和无穷性:
成员性: 利用 CNF 范式, 有CYK算法检查串 w 是否属于 L
例：CNF G G G 如下, 用 CYK 算法判断 b b a b a a ∈ L ( G ) bbabaa ∈ L(G) bbabaa∈L(G)?
解：
S
→
A
B
∣
B
C
S → AB | BC
S→AB∣BC
A
→
B
A
∣
a
A → BA | a
A→BA∣a
B
→
C
C
∣
b
B → CC | b
B→CC∣b
C
→
A
B
∣
a
C → AB | a
C→AB∣a
填写最下层（单个终结符是否有可达）
计算上面若干行
结果
因为 S ∈ X 16 = { S , A } S ∈ X_{16} = \{S, A\} S∈X16={S,A}, 所以 b b a b a a ∈ L ( G ) bbabaa ∈ L(G) bbabaa∈L(G)
| FA | PDA | TM |
|---|---|---|
 |
 |
 |
| ( Q Q Q, Σ \Sigma Σ, δ \delta δ, q 0 q_0 q0, F F F) | ( Q Q Q, Σ \Sigma Σ, Γ \Gamma Γ, δ \delta δ, q 0 q_0 q0, z 0 z_0 z0, F F F) | ( Q Q Q, Σ \Sigma Σ, Γ \Gamma Γ, δ \delta δ, q 0 q_0 q0, B B B, F F F) |
与有穷自动机区别：
- 可修改（必须修改，但可以相同）
- 可向左或向右移动输入带
- 有空格符号
例：设计识别 { 0 n 1 n ∣ n ≥ 1 } \{0^n1^n | n ≥ 1\} {0n1n∣n≥1} 的图灵机
解：
M
=
(
{
q
0
,
q
1
,
q
2
,
q
3
,
q
4
}
,
{
0
,
1
}
,
{
0
,
1
,
X
,
Y
,
B
}
,
δ
,
q
0
,
B
,
{
q
4
}
)
M = (\{q0, q1, q2, q3, q4\}, \{0, 1\}, \{0, 1, X, Y, B\}, δ, q_0, B, \{q4\})
M=({q0,q1,q2,q3,q4},{0,1},{0,1,X,Y,B},δ,q0,B,{q4})
图灵机虽有无穷长的带, 但经过有限步, 带上非空内容总是有限的. 因此用全部非空符号、当前状态及带头位置, 定义图灵机的瞬时描述(ID)为
X
1
X
2
⋅
⋅
⋅
X
i
−
1
q
X
i
X
i
+
1
⋅
⋅
⋅
X
n
X_1X_2 · · · X_{i−1}qX_iX_{i+1} · · · X_n
X1X2⋅⋅⋅Xi−1qXiXi+1⋅⋅⋅Xn
如果
δ
(
q
,
X
i
)
=
(
p
,
Y
,
L
)
δ(q, Xi) = (p, Y, L)
δ(q,Xi)=(p,Y,L), 定义 ID 转移为
X
1
⋅
⋅
⋅
X
i
−
1
q
X
i
⋅
⋅
⋅
X
n
⊢
X
1
⋅
⋅
⋅
X
i
−
2
p
X
i
−
1
Y
X
i
+
1
⋅
⋅
⋅
X
n
X_1 · · · X_{i−1}qX_i · · · X_n ⊢ X_1 · · · X_{i−2}pX_{i−1}YX_{i+1} · · · X_n
X1⋅⋅⋅Xi−1qXi⋅⋅⋅Xn⊢X1⋅⋅⋅Xi−2pXi−1YXi+1⋅⋅⋅Xn
续例：设计识别 { 0 n 1 n ∣ n ≥ 1 } \{0^n1^n | n ≥ 1\} {0n1n∣n≥1} 的图灵机, 接受 0011 的 ID 序列
解：
q
00011
⊢
X
q
1011
⊢
X
0
q
111
⊢
X
q
20
Y
1
⊢
q
2
X
0
Y
1
⊢
X
q
00
Y
1
⊢
X
X
q
1
Y
1
⊢
X
X
Y
q
11
⊢
X
X
q
2
Y
Y
⊢
X
q
2
X
Y
Y
⊢
X
X
q
0
Y
Y
⊢
X
X
Y
q
3
Y
⊢
X
X
Y
Y
q
3
B
⊢
X
X
Y
Y
B
q
4
B
q00011 ⊢ Xq1011 ⊢ X0q111 ⊢ Xq20Y1 ⊢ q2X0Y1 ⊢ Xq00Y1 ⊢ XXq1Y1 ⊢ XXYq11 ⊢ XXq2Y Y ⊢ Xq2XYY ⊢ XXq0YY ⊢ XXYq3Y ⊢ XXYYq3B ⊢ XXYYBq4B
q00011⊢Xq1011⊢X0q111⊢Xq20Y1⊢q2X0Y1⊢Xq00Y1⊢XXq1Y1⊢XXYq11⊢XXq2YY⊢Xq2XYY⊢XXq0YY⊢XXYq3Y⊢XXYYq3B⊢XXYYBq4B
如果 M 是一个图灵机，则 M 接受的语言为
L
(
M
)
=
{
w
∣
w
∈
Σ
∗
,
q
0
w
⊢
∗
α
p
β
,
p
∈
F
,
α
,
β
∈
Γ
∗
}
L(M) = \{w | w ∈ Σ^∗, q_0w ⊢*αpβ, p ∈ F, α, β ∈ Γ^∗\}
L(M)={w∣w∈Σ∗,q0w⊢∗αpβ,p∈F,α,β∈Γ∗}
如果 L L L 是图灵机 $M $的语言, 即 L = L ( M ) L = L(M) L=L(M), 则称 L L L 是递归可枚举语言.
一般假定, 当输入串被接受时, 图灵机总会停机
然而, 对于不接受的输入, 图灵机可能永远不停止
对接受和不接受的输入, 都保证停机的图灵机, 所接受的语言称为递归语言
例：Compute the function nomus (m, n)=max(m-n,0)
解：
例：Construct a TM to compute m×n
3 × 2 = 2 + 2 + 2
