编译原理--有限自动机
(4)S∈K,是唯一的初态;
(5)Z是K的子集,是一个终态集,终态也称为可接收状态或 结束状态。
12
确定的有穷自动机DFA的表示
3.2.1 状态转换图
设DFA有m个状态,n个输入字符,那么这个图含有m 个状态结,每个结点最多有n条箭弧射出和别的结点相连接, 每条弧用Σ中的一个不同输入符号作记号。整个图含有唯一 的一个初态和若干个(可以0个)终态结。
10
3.2 有穷自动机的形式定义
DFA: Deterministic Finite Automata NFA: Nondeterministic Finite Automata
DFA的定义
定义3.1 一个确定的有穷自动机(DFA) M是一个五元组: M = ( K, Σ, f, S, Z )
(1)K是一个非空有穷集合,它的每一个元素称为一个状态;
解:该DFA M的状态图:
0
a
b b
1
a 2
a
3 b
a, b
14
确定的有穷自动机DFA的表示(续)
3.2.2 状态转换矩阵
矩阵的行表示状态,列表示输入字符,矩 阵元素表示相应的状态行在输入字符列下的新 的状态,即f(k,a)的值。
15
例2(题同1)
解:该DFA M的矩阵表示
状态 0 1 2 3 字符 a 1 3 1 3 b 2 2 3 3
例1:(1)到此为止是偶数个a和偶数个b; (2)到此为止是奇数个a和偶数个b; (3)到此为止是偶数个a和奇数个b; (4)到此为止是奇数个a和奇数个b。 根据每种可能性设计一个状态,并根据可能的输入 符号来设计状态之间的转移条件。 a a 2 b b b 3 a a b
1
4
30
设计有限自动机(续)
例2:设计有限自动机M,识别含有00作为子串的 所有{0,1|*上的字符串组成的语言。 如:0010,1001,110001001 解:3种可能性: (1)到此为止未看到模式“00”的任何符号;
(2)到此为止看见了一个0;
(3)到此为止已经看见整个模式“00”。
31
设计有限自动机(续)
例2自动机的状态转换图为:
1 q 1 0 q0 0 0,1 q00
或者为(NFA):
0,1 q 0 q0 0
0,1
q00
32
NFA和DFA的关系
DFA是NFA的一个特例。 • • 对于每个NFA M,存在一个DFA M’,使得L(M)=L(M’) 对于任何两个有穷自动机M和M’,如L(M)=L(M’)则称 M和M’是等价的。
问题:
6
例 过河问题 状态转换图
起始 MWGC-φ
g g g g φ-MWGC g MGC-W MG-WC m m
WC-MG
m m
MWC-G w
w c
c W-MGC
g g
C-MWG g c w c
MWG-C w
G-MWC
7
有穷自动机(FA)
数字系统:可以从一个状态移动到另一个状态;每次 状态转换,都上由当前状态及一组输入符号确定的;可以 输出某些离散的值集。
25
补充:递归思想构造文法
在某些复杂的语言中,字符串可能包含一种结构, 它递归地作为另一种(或者同一种)结构的一部分而出 现,可利用递归思想来构造对应的文法。 例1:定义语言L={ω| ω中a和b的个数相同}的文法。 解:先构造出基础情况的文法: S-> ab | ba | ε 再递归地构造出归纳情况的文法(新的生成式不能改变a和 b的个数关系): S-> Sab | aSb | abS | Sba | bSa | baS
0 0
0
1
0
a b b
1 a
a 3
a, b
2
b
16
3.2.3 有关自动机术语
(1)道路:对于Σ*中的任何字α,若存在一条从初态到某终 态的路径。
(2)识别:道路上所有弧的标记连接成的字等于α,则称α 可为DFA M所识别(所接受)。
即若t∈Σ*, f(S,t)=P,其中S为DFA M的初始状态, P∈Z(终态集)。 若M的初态结同时也是终态结,则空字ε可为M所识别, 即Q∈K, f(Q, ε)=Q (3)运行: f(Q, t1t2) = f(f(Q, t1), t2),其中Q∈K, t1t2为输入字符 串,且t1 ∈Σ,t1t2 ∈Σ*
17
例3
题:试证abba可为例1的DFA M所识别(所接受)。
a 1 b b 2 a b a 3 a, b
解:∵f(0, abba) Nhomakorabea
0
= f(f(0,a), bba)= f(1, bba)
= f( f(1,b), ba) = f(2, ba) = f(f(2,b), a) = f(3, a) =3 ∴ 得证
(2)Σ是一个有穷字母表,它的每一个元素称为一个输入字 符; Σ也称为输入符号字母表
11
确定的有穷自动机DFA的定义(续)
(3) f是从Σ×K到K的单值部分映射;
f(ki,a)=kj, 其中ki∈K,kj∈K
说明:当前状态为ki ,输入字符a时,将转换到下一个 状态kj ,把kj称为ki的一个后继状态。 DFA的确定性就表现在f是单值函数,即对任意状态k∈K, 输入符号a∈Σ,f(k,a)唯一确定一个状态。
16种状态中的某些状态,是不应该引入系统的,例如 GC-MW,有关死活。
人所进行的摆渡活动,可作为系统的输入。人可单独 过河(输入为M),带着狼过河(输入为W),带着羊过 河(输入为G)或者是带着菜过河(输入为C)。 问题:初始状态应该是什么?终止状态应该是什么?
5
例 过河问题 分析(续)
初始状态:MWGC-φ;终止状态:φ-MWGC。 g MWGC-φ WC-MG
3
例 过河问题
题目
一个人带着一头狼、一头羊以及一棵青菜,处于河的 左岸,需要渡到河的右岸。有一条小船,每次只能携带人 和其余的三者之一。不能让狼和羊单独在一起,无论在左 岸还是右岸,否则狼会吃掉羊。同样,也不能让羊和青菜 单独一起。 如何才能安全渡过河呢?
4
例 过河问题 分析
观察每次摆渡后河两岸的局势,使问题模型化。 人(M),狼(W),羊(G),菜(C)。存在有16 种子集,用连字号”-”连接子集的对偶表示状态,例如: MG-WC,表示:人和羊在左岸,狼和菜在右岸。
24
有关非确定有穷自动机的术语
对于Σ*中的任何一个串t可被NFA M识别是指: 若对这个字(串)t存在一条从某个初态结到某一 个终态结的道路,且这条道路上所有弧的标记字依 序连接起来的字(不理睬那些标记为ε的弧)等于t, 则t可识别(或可接受) 若M的某些结点既是初态结也是终态结,或存 在一条从某个初态结到某个终态结的ε道路,则空 字ε可为M所识别(所接受)。
20
3.2.5 不确定的有穷自动机(NFA)的定义
定义3.4 一个不确定的有穷自动机NFA N也是一个五元组: M = ( K, Σ, f, S, Z ) (1)K是一个有穷集合,它的每一个元素称为一个状态; (2)Σ是一个有穷字母表,它的每一个元素称为一个输入字符; Σ也称为输入符号字母表 (3) f是一个K×Σ*到K的子集的映射: f : K×Σ*→2k (4)S是K的子集,是非空的初态集; (5)Z是K的子集,是一个终态集,也称可接收状态或结束状态。
S->aaS | bbS | abA | baA ……
A->aaA | bbA | abS | baS | ε……
27
补充:如何设计有限自动机
如同文法的设计,自动机的设计也是一个创造过程。 有一种做法,在设计各种类型的自动机时都很有帮助, 即采用一种心理上的技巧,把自己放在要设计的机器的 位置上,考虑自己该如何实现自动机的任务。 假定自己是一台有限自动机,接受到一个输入符号 串时,必须确定到目前为止所看到的字符串是否可为该 自动机所识别。为了能够判断这一点,必须估算出识别 时需要记住哪些关键的东西。 为什么不记住所有看到的东西呢?因为你是一台有 限自动机,只有有限个状态,而这些状态是你记住事情 的唯一办法。输入串可能很长,而你不可能记住所有的 事情。 幸运的是,许多语言只需要记住某些关键的信息就 可以了。
FA:一个状态集合;状态间的转换规则;通过读头来 扫描的一个输入符号串。 读头:从左到右扫描符号串。移动(扫描)是由状态 转换规则来决定的。
8
读头
一个FA的例子
d d d ;
数字
+ d d .
输入符号串
S
数字
B
数字
.
数字
接收:若扫描完输入串, 且在一个终止状态上结 束。
+
A
.
H
数字
-
阻塞:若扫描结束但未 停止在终止状态上;或 者为能扫描完输入串 (如遇不合法符号)。
26
递归思想构造文法 (续)
例1:求一个文法G,使得L(G)即该文法的语言是奇数个 a和奇数个b的组合。 解: 因为语言是奇数个a和奇数个b的组合,所以打头 的最小语言有四种组合: aa bb ab ba 定义S和A,S是表示奇数个 a和奇数个b的组合,而 A是表示偶数个a和偶数个b的组合。 开始递归构造文法:
18
3.2.4 有关确定有穷自动机的结论
把DFA M所能接受的所有字(字的全体)记 为L(M)。
Σ上的一个字集V∈Σ*是正规的,当且仅当存 在一个Σ上的确定有穷自动机M,使得L(M)=V。
19
有限自动机识别的语言 例子
例:下图中的自动机所能识别的语言是什么?
b a q1 a
q0 b
a
q3 q2 b
分类:确定的有穷自动机(DFA) 不确定的有穷自动机(NFA)