1
11.2 有穷自动机
? 确定型有穷自动机 (DFA)
? 非确定型有穷自动机 (NFA)
? 带 ε转移的 NFA(ε-NFA)
2
确定型有穷自动机
定义 确定型有穷自动机 (DFA)是一个有序 5元组
M = ?Q,Σ,δ,q0,F ?,其中
(1) 状态集合 Q,非空有穷集合
(2) 输入字母表 Σ,非空有穷集合
(3) 状态转移函数 δ:Q?Σ→ Q
(4) 初始状态 q0?Q
(5) 终结状态集 F?Q
控制器
an … ai … a2 a1
3
DFA接受的语言
把 δ扩张到 Q?Σ*上 δ*:Q?Σ*→ Q,递归定义如下
?q?Q,a?Σ和 w?Σ*
δ*(q,ε)=q
δ*(q,wa)= δ(δ*(q,w),a)
定义 ?w?Σ*,如果 δ*(q0,w)?F,则称 M接受 w,
M接受的字符串的全体称作 M接受的语言,记作
L(M),即
L(M)={ w?Σ*| δ*(q0,w)?F }
4
DFA接受的语言 (续 )
例 1 M= ?{q0,q1},{a},δ,q0,{q1}?
δ(q0,a)=q1,δ(q1,a)=q0
L(M)={a2k+1 | k?N}
?
?
?
??
为偶数
为奇数
0
1
0
n,q
n,q
)a,(qδ n
?
?
?
??
为偶数
为奇数
1
0
1
n,q
n,q
)a,(qδ n
5
非确定型有穷自动机
定义 非确定型有穷自动机 (NFA)
M =〈 Q,Σ,δ,q0,F 〉,
其中 Q,Σ,q0,F 的定义与 DFA 的相同,而
δ,Q ?Σ→ P(Q)
6
实例
δ → q0 q1 *q2 q3 *q4
0
1
{q0,q3} ? {q2} {q4} {q4}
{q0,q1} {q2} {q2} ? {q4}
例 2 一台 NFA
7
NFA接受的语言
?
),(
),(
wqp
ap
?? ?
?
δ*:Q?Σ*→ Q 递归定义如下, ?q?Q,a?Σ 和 w?Σ*
δ*(q,ε)={q}
δ*(q,wa)=
定义 ?w?Σ*,如果 δ*(q0,w)∩F≠?,则称 M接受 w,
M接受的字符串的全体称作 M接受的语言,记作
L(M),即
L(M)={ w?Σ*| δ*(q0,w)∩F≠? }
8
例 2 (续 )
L(G) = { x00y,x11y | x,y?{0,1}*}
w δ*(q0,w)
1
10
101
1011
10110
{q0,q1}
{q0,q3}
{q0,q1}
{q0,q1,q2}
{q0,q2,q3}
9
DFA与 NFA的等价性
用 M?=?Q?,Σ,δ?,q0?,F? ? 模拟 M=?Q,Σ,δ,q0,F ?
Q?=P(Q),q0?={q0}
F?={ A?Q | A∩F≠?}
?A?Q 和 a?Σ,
?
Ap
apaA
?
?? ),(),( ??
定理 对每一个 NFA M 都存在 DFA M ?使得
L(M)=L(M ?)
10
模拟实例
NFA M DFA M?
δ 0 1
→ q0
q1
*q2
{q0,q1} {q0}
{q2} ?
? ?
δ? 0 1
→ {q0}
{q1}
*{q2}
{q0,q1}
*{q0,q2}
*{q1,q2}
*{q0,q1,q2}
?
{q0,q1} {q0}
{q2} ?
? ?
{q0,q1,q2} {q0}
{q0,q1} {q0}
{q2} ?
{q0,q1,q2} {q0}
? ?
11
模拟实例 (续 )
δ?? 0 1
→ {q0}
{q0,q1}
*{q0,q1,q2}
{q0,q1} {q0}
{q0,q1,q2} {q0}
{q0,q1,q2} {q0}
不可达状态,从初始状态出发永远不可能达到的状态
删去所有的不可达状态,不会改变 FA接受的语言,
如 M?中的 {q1},{q2},{q0,q2},{q1,q2}和 ?都是不可达状态,
删去这些状态得到 M??
12
带 ε转移的非确定型有穷自动机
ε转移, 不读如何符号,自动转移状态,
ε-NFA,δ:Q?(Σ∪ {ε})→ P(Q)
定理 对每一个 ε-NFA M 都存在 DFA M ? 使得
L(M)=L(M?)
DFA,NFA 和 ε-NFA 接受同一个语言类
13
用 DFA模拟 ε-NFA
设 ε-NFA M=?Q,Σ,δ,q0,F ?,q?Q
q的 ε闭包 E(q),从 q出发,经过 ε转移能够到达的所
有状态,递归定义如下
(1) E(q)包含 q;
(2) 如果 p?E(q),则 δ(p,ε)?E(q),
例 3 ε-NFA M
δ 0 1 ε
→ q0
q1
*q2
{q1} ? {q2}
? {q2} ?
? ? {q0}
q E(q)
q0
q1
q2
{q0,q2}
{q1}
{q0,q2}
14
用 DFA模拟 ε-NFA(续 )
模拟的方法与用 DFA模拟不带 ε的 NFA的方法基本相同,
只是要用 E(q)代替 q,
用 DFA M?=?Q?,Σ,δ?,q0?,F? ?模拟 ε-NFA M=?Q,Σ,δ,q0,F ?
Q?=P(Q),q0?=E(q0)
F ?={A?Q | A∩F≠?}
?A?Q和 a?Σ,
?
Aq
aptqEptptEraA
?
?????? )},(),(,|)({),( ?? 使
构造 DFA M?时 不需要对不可达状态进行计算,做法如下, 从 q0?=
E(q0)开始,对每一个 a?Σ计算 δ?的值,然后对每一个新出现的子
集计算 δ?的值,重复进行,直至没有新的子集出现为止,
15
模拟实例 —— 例 3(续 )
L(M)=L(M?)={ (01)n | n?0 }
δ 0 1 ε
→ q0
q1
*q2
{q1} ? {q2}
? {q2} ?
? ? {q0}
δ? 0 1
→ *{q0,q2}
{q1}
?
{q1} ?
? {q0,q2}
? ?
ε-NFA M DFA M?
?
ε ε
16
11.3 有穷自动机和正则文法
的等价性
? 用 ε-NFA模拟右线性文法
? 用右线性文法模拟 DFA
17
有穷自动机和正则文法的等价性
定理 设 G是右线性文法,则存在 ε-NFA M 使得
L(M)=L(G); 设 M是 DFA,则存在右线性文法 G使
得 L(G)= L(M),
定理 下述命题是等价的,
(1) L是正则语言 ;
(2) 语言 L能由右线性文法生成 ;
(3) 语言 L能由左线性文法生成 ;
(4) 语言 L能被 DFA接受 ;
(5) 语言 L能被 NFA接受 ;
(6) 语言 L能被 ε-NFA接受,
18
用 ε-NFA模拟右线性文法
设右线性文法 G=?V,T,S,P ?
ε-NFA M=?Q,Σ,δ,q0,F ?构造如下,
Q=V∪ {qf },q0={S},F={qf },
Σ={ α?T *-{ε} | 存在 A→ αB?P或 A→ α?P }
?A?V和 α?Σ∪ {ε},
若 A→ αB?P,则 δ(A,α)中含有 B;
若 A→ α?P,则 δ(A,α)中含有 qf;
?α?Σ∪ {ε},δ(qf,α)= ?
19
模拟实例
L(G)=L(M)={ (11)m0n | m?1,n?0 }
G =?V,T,S,P ?
V={A,S}
T={0,1}
P,S→11 S
S→11 A
A→0 A
A→ ε
ε-NFA M=?Q,Σ,δ,S,{qf} ?
Q ={A,S,qf}
Σ ={11,0}
δ 11 0 ε
→ S
A
*qf
{S,A} ? ?
? {A} {qf}
? ? ?
20
用 右线性文法模拟 DFA
设 DFA M=?Q,Σ,δ,q0,F ?
右线性文法 G=?V,T,S,P ?构造如下,
V=Q,T=Σ,S=q0
?q?Q和 α?Σ,
若 δ(q,a)=p,则有产生式 q→ ap
若 q?F,则有产生式 q→ ε
21
模拟实例
δ 0 1
→ q0
q1
*q2
q1 q0
q2 q1
q0 q2
DFA M G =?V,T,S,P?
V={q0,q1,q2},T={0,1},S= q0
P,q0→ 0q1 q0→ 1q0
q1→ 0q2 q1→ 1q1
q2→ 0q0 q2→ 1q2
q2→ ε
L(M)=L(G),它们是所有含 3k+2
(k?0)个 0的 0,1串组成的集合