离散数学11.2-3.ppt

有穷自动机?确定型有穷自动机(DFA) ?非确定型有穷自动机(NFA) ?带?转移的 NFA( ?-NFA) 2确定型有穷自动机定义确定型有穷自动机(DFA) 是一个有序 5元组 M = ?Q,?,?,q 0 ,F ?, 其中(1) 状态集合 Q : 非空有穷集合(2) 输入字母表?: 非空有穷集合(3) 状态转移函数?:Q?Σ→Q (4) 初始状态 q 0?Q (5) 终结状态集 F?Q 控制器 a n… a i… a 2a 1 3 DFA 接受的语言把?扩张到 Q??*上?*:Q??*→Q, 递归定义如下?q? Q, a ??和w??*?*(q,?)=q?*(q, wa )= ?(?*(q,w),a) 定义?w??*,如果?*(q 0,w)?F, 则称 M接受 w. M 接受的字符串的全体称作 M接受的语言,记作 L(M ), 即L(M )={ w??* | ?*(q 0,w)? F } 4 DFA 接受的语言(续) 例1 M = ?{q 0, q 1 },{a }, ?,q 0,{q 1}??(q 0, a )=q 1, ?(q 1, a )=q 0L(M )={ a 2k +1 | k? N} ?????为偶数为奇数 0 1 0n,q n,q)a, (qδ n?????为偶数为奇数 1 0 1n,q n,q)a, (qδ n 5非确定型有穷自动机定义非确定型有穷自动机(NFA) M =〈Q,?,?,q 0 ,F 〉,其中 Q,?, q 0 , F 的定义与 DFA 的相同, 而?: Q ??→P(Q) 6实例{q 0 , q 3 } ?{q 2 } {q 4 } {q 4} {q 0 , q 1 } {q 2 } {q 2 } ?{q 4} 01 →q 0q 1*q 2 q 3 *q 4 ?例2 一台 NFA 7 NFA 接受的语言?),(),( wqpap ?????*:Q??*→Q递归定义如下: ?q? Q, a ??和w??* ?*(q,?)={ q}?*(q, wa )= 定义?w??*,如果?*(q 0 ,w)∩F≠?, 则称 M接受 w. M 接受的字符串的全体称作 M接受的语言,记作 L(M ), 即L(M )={ w?Σ* | ?*(q 0 ,w)∩F≠?} 8例2 ( 续)L(G ) = { x00y, x11y | x,y ?{0,1} *} {q 0, q 1}{q 0, q 3}{q 0, q 1}{q 0, q 1 , q 2}{q 0, q 2 , q 3} 110 101 1011 10110 δ*(q 0 ,w)w9 DFA 与 NFA 的等价性用M?=?Q?,?,??,q 0?,F ??模拟 M=?Q,?,?,q 0 ,F ? Q ?=P(Q ), q 0?={q 0} F ?={ A?Q | A∩F≠?} ?A? Q 和a?Σ,? ApapaA ???),(),(??定理对每一个 NFA M都存在 DFA M ?使得 L(M )=L( M ?) 10 模拟实例 NFA M DFA M?{q 0, q 1 } { q 0} {q 2 } ???→q 0 q 1*q 20 1 δ{q 0, q 1 } { q 0} { q 2 } ???{q 0,q 1,q 2 } { q 0} { q 0,q 1 } { q 0} { q 2 } ?{q 0,q 1,q 2 } { q 0}??→{q 0}{q 1}*{q 2}{q 0,q 1}*{q 0,q 2}*{q 1,q 2}*{q 0,q 1,q 2}? 0 1 δ?