离散数学(形式语言与自动机).pptVIP

11.2 有穷自动机 确定型有穷自动机(DFA) 非确定型有穷自动机(NFA) 带ε转移的NFA(ε-NFA) NFA接受的语言 例2 (续) L(G) = { x00y, x11y | x,y?{0,1}*} DFA与NFA的等价性 用M?=?Q?,Σ,δ?,q0?,F? ? 模拟 M=?Q,Σ,δ,q0,F ? Q?=P(Q), q0?={q0} F?={ A?Q | A∩F≠?} ?A?Q 和 a?Σ, 带ε转移的非确定型有穷自动机 ε转移: 不读如何符号, 自动转移状态. ε-NFA: δ:Q?(Σ∪{ε})→P(Q) 定理 对每一个ε-NFA M 都存在DFA M ? 使得 L(M)=L(M?) DFA, NFA 和 ε-NFA 接受同一个语言类 用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 用DFA模拟ε-NFA(续) 模拟的方法与用DFA模拟不带ε的NFA的方法基本相同, 只是要用E(q)代替q. 模拟实例——例3(续) L(M)=L(M?)={ (01)n | n?0 } 11.3 有穷自动机和正则文法 的等价性 用ε-NFA模拟右线性文法 用右线性文法模拟DFA 有穷自动机和正则文法的等价性 定理 设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接受. 用ε-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 ,α)= ? 模拟实例 L(G)=L(M)={ (11)m0n | m?1, n?0 } 用右线性文法模拟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→ε 模拟实例 * * 确定型有穷自动机 定义 确定型有穷自动机(DFA)是一个有序5元组 M = ?Q,Σ,δ,q0,F ?, 其中 (1) 状态集合Q: 非空有穷集合 (2) 输入字母表Σ: 非空有穷集合 (3) 状态转移函数δ:Q?Σ→Q (4) 初始状态 q0?Q (5) 终结状态集 F?Q 控制器 an … ai … a2 a1 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 } DFA接受的语言(续) 例1 M= ?{q0, q1},{a}, δ,q0,{q1}? δ(q0, a)=q1, δ(q1, a)=q0 L(M)={a2k+1 | k?N} 非确定