设 ∑ = {a,b}，L={ 不包含子串 aba 的串 } 1 能表达语言L的正规式 2 能识别语言L的NFA 3 能识别语言L的DFA 4 能识别语言L的状态最少的DFA

不包含子串 aba 的串 RE: b* ( a | bbb* )* b*

不确定的有穷状态自动机NFA NFA M＝( S，∑，δ，S0，F ) 1 Ｓ是一个有限集 它的每个元素称为一个状态 2 ∑ 是一个有穷字母集 它的每个元素称为输入字符 3 δ 是一个从Ｓｘ ∑ -> S的子集的映射 δ:S ｘ ∑* -> T（T属于S） 4 S0 属于S 是一个非空的初态集 5 Ｆ 属于S 是一个终态集（可空）*

根据RE画出状态转换图 NFA M=({1,2,3,4,5},{a,b}, δ ,{1,2,3,4},{5}) {1,2,3,4,5}表示五个状态 {a,b}表示输入字符 δ是一个子集的映射 δ(1,a)={2} δ(1,b)={1,2} δ(2,a)={2,5} δ(2,b)={3,5} δ(3,a)={∅} δ(3,b)={2,4} δ(4,a)={2} δ(4,b)={2,4} δ(5,a)={∅} δ(5,b)={5} {1,2,3,4}表示该NFA的初态集 {5}表示该NFA的终态集

定义一：状态集I的ε闭包，记为ε_CLOSURE(I) ⅰ.若s∈I,则s∈ε_CLOSURE(I)； ⅱ.若s∈I，则由s出发经任意条ε弧而能够到达的任何状态s´∈ε_CLOSURE(I) 定义二：对状态集I和a∈Σ，定义： Ia= ε_CLOSURE(J) ；其中J是那些可从I中某一结点出发经过一条a弧而到达的状态结点的集合

设I={1} 则I′= ε_CLOSURE(I) = {1,2,5} p.s 这里含义是写初态 由于1到2到5都是ε 所以要加入此初态集 DFA的初态是唯一的 然后构建状态转换表

将ε_CLOSURE(I) = {1,2,5} 写入表中 然后 {1,2,5} 分别输入a b看能到达什么状态 1输入a 哪里也到达不了 但是可以带ε转移 到达2 2输入a 能够到达自身 同时可以带ε转移 到达5 5输入a 哪里也到达不了 于是在{1,2,5}和a的交界处填入{2,5} 1输入b 能够到达自身 同时可以带ε转移 到达2 2输入b 可以到达3 同时可以带ε转移 到达5 5输入b 可以到达自身 于是在{1,2,5}和b的交界处填入{1,2,3,5}

此后同理 然后将{2,5} 和 {1,2,3,5}填入第一列中 表示作为一个新的状态 继续查看{2,5} 和 {1,2,3,5}分别输入a b看能到达什么状态 这里就不再赘述 我们来看这里的一个小陷阱 到{3,5}这一行 输入a 哪里也到不了 所以写空 输入b 3输入b到达4 5输入b到达5 那么2是哪里来的呢？ 这就是带ε转移 NFA中特有的 3输入b到达4后 4检测到到2中间为ε 所以转移到状态2 解释完毕

每次有一个新的子集出现 一定要把它加入到左边第一列作为一个新的状态 这其实就是NFA到DFA的转换实质-让NFA的 多值映射&带空转移 消失 这两者是NFA不确定的体现 构造完成 现在就知道后面的小格留出来干嘛的？ 就是为了写上它们新的状态 将第一行的子集按顺序命名为后面的新状态 A={1,2,5} 以此类推 然后补齐后面的转移后的状态 完成 下一步就是根据这份状态转移矩阵画出状态转换图 就可以直观的看到转换后的DFA 这就是我们得到的DFA

等价状态： 若分别从状态 s 和 t 出发而停于终态能读出同一个串α 则称 s t 为等价状态 反之则称为可区别状态 如何寻找等价状态？ 逆向思维：去掉那些一定不等价的（可区别状态） 剩下的就是等价的

DFA最小化的第一步 就是先对DFA的状态做一个粗略的划分 上面我们没有讲到终态的确定 再来回顾一下最后的这张表 由于NFA中的终态为{5} 所以这张表最左边一列 只要含5的就是终态 这也是不管遇到什么题 DFA终态的确定法-找NFA的终态 然后看状态转换表最左边一列哪个含有NFA的终态 那么这个就是DFA的终态 由此我们通过这张表看出 DFA的终态集为{A,B,C,D,E,F,G} 因为它们对应的NFA子集都含有{5}

然后就是对DFA的状态做一个粗略的划分 我们一般常用初态和终态先划分 那么这道题我们怎么划分呢？ 还是看状态转换表 由于D比较特殊 它输入a没有到任何状态 所以我们就把这个特殊的挑出来 粗略划分为 L1：{D} L2：{A,B,C,E,F,G} 然后继续划分 看L2有哪些状态能够到达特殊的L1区域呢？ L2：{A,B,C,E,F,G}又划分为 L21：{B} L22：{A,C,E,F,G} 可以看出 当B输入b时 到达L1 而A,C,E,F,G输入b时 还在L2内

我们再来划分L22：{A,C,E,F,G} 同时输入a 都指向L21中的B 同时输入b 指向的状态都在L22里 而且不管跳几个a 几个b 它们所指向的区域都是相同的 所以这五个状态相当于一个状态 就将它们合并

由此划分为{A,C,E,F,G} {B} {D} 然后我们将它们重新命名一下 {A,C,E,F,G}命名为SA {B}命名为SB {D}命名为SD 然后根据未最小化的DFA 画出最小化的DFA {A,C,E,F,G}合并为一个状态 所以原来D指向F的边 现在指向A 同时{A,C,E,F,G}内部也有b互相传递 所以给A一个b*（即b的闭包） 让它自己转着玩 最小化也搞定 结束！