自动机重点复习题.pdf

第二章 Give DFA’s accepting the following language: The set of all string ending in 00. The intuitive meanings of states A, B, and C are that the string seen so far ends in 0, 1, or at least 2 zeros. 状态 A, B ，C 分别表示以１, ０和00 结尾的串的状态。 0 1 -A B A B C A *C C A Convert to a DFA the following NFA. 下表就是利用子集构造法将NFA 转化成的DFA 。其中构造的子集有：A = {p}; B = {p,q}; C = {p,r}; D = {p,q,r}; E = {p,q,s}; F = {p,q,r,s}; G = {p,r,s}; H = {p,s}. 0 1 -A B A B D C C E A D F C *E F G *F F G *G E H *H E H ε-NFA(convert to DFA 、ε-closure) (a): 根据状态的ε 闭包的的性质。求得， p 的ε 闭包：{p}； q 的ε 闭包：{p,q}； r 的ε 闭包：{p,q,r}。 b) 由于输入a 状态总是保持不变，因此只需考虑输入b 和c 的情况。可以看出， 从状态p 第一次到r 且只经过b ，c 和ε 转移的路径为bb, bεc 和 c ；到r 之后， 读入b 仍可回到r ，读入c 回到p ，则可通过继续读入串bb, bc 和 c 回到r 。 因此，每一个由b 和c 组成的长度小于等于3 的串可以被接受，除了串b 不能接 受。向这些串中插入a，并保持长度小于等于3，就会得到所有由a，b ，c 组成 的，至多含有一个a 的可被接受的串。由一个c 和两个a 组成的任意串也是可以 被接受的。其它的串均被拒绝。 由初始状态，即p 的ε 闭包或者{p}，有3 个状态可以达到。令A = {p}, B = {p,q}, C = {p,q,r} 。转移表如下： a b c -A A B C B B C C *C C C C 第三章 R (0) R (1) ij ij a) 下面就是所有 R0 的表达式；我们只写出下标： R11 = ε+1；R12 = 0; R13 = (phi); R21 = 1; R22 = ε; R23 = 0; R31 = (phi); R32 = 1; R33 = ε+0. b) 下面就是所有 R(1) 的表达式；我们只写出下标：R11 = 1*; R12 = 1*0; R13 = phi; R21 = 1