资源预览内容
第1页 / 共11页
第2页 / 共11页
第3页 / 共11页
第4页 / 共11页
第5页 / 共11页
第6页 / 共11页
第7页 / 共11页
第8页 / 共11页
第9页 / 共11页
第10页 / 共11页
亲,该文档总共11页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
第二章 Give DFAs 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, bc 和 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 第三章 Rij(0) Rij(1) 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 = 11*; R22 = +11*0; R23 = 0; R31 = phi; R32 = 1; R33 = +0. e): Here is the transition diagram 转移图: 如果消除状态 q2,有: q1 到 q3 的正则表达式:1 + 01 + 00(0+10)*11*00(0+10)* Regular expression for: (1) the set of string that consists of alternating 0s and 1s. (+1) (01)*(+0) (2) a,b,c上包含至少一个 a 和至少一个 b 的集合。 首先考虑第一个 a 在第一个 b 的前面,然后再考虑相反的情况。表达式为: c*a(a+c)*b(a+b+c)* + c*b(b+c)*a(a+b+c)* (3) 使得每对相邻的 0 都出现在任何一对相邻的 1 之前的所有 0 和 1 的串集 (10+0)*(01+1)*(+0) 第四章 只有只有1构成且长度为素数的所有串构成的语言不是正则语言构成且长度为素数的所有串构成的语言不是正则语言 00n n1010n n | n=1| n=1,证明下列语言不是正则的 令n为泵引理常数 (这个n与语言L的定义中的局部变量n无关) 。 设w = 0n10n。 把 w 打断为 w = xyz,满足|xy| =1,context-free grammar S - 0S1 | 01 aibjck | i!=j or j!=k S - AB | CD A - aA | B - bBc | E | cD C - aCb | E | aA D - cD | E - bE | b 意思如下: A 产生 0 或者一个或多个 a。. D 产生 0 或者一个或多个 c。 E 产生一个或多个 b。 B 产生式中 b 和 c 的个数一样多, 然后产生一个或多个 b (通过 E) 或 一 个或多个 c 通过 cD)。即, B 产生这样的字符串 b*c* ,其中 b 和 c 的 个数不相等。 同样, C 产生 a 和 b 个数不相等的字符串。 因此,AB 产生字符串 a*b*c* ,并且 b 和 c 的数目不同; CD 产生字 符串 a*b*c*并且 a 和 b 的数目不同。 第六章 Design a PDA that processes sequence of ifs and elses, where i stands for if and e stands for else. 0n1n | n=1,Design a PDA that can accept the following language: 以空栈方式接受。符号 X 表示符号 0。初始状态 q 中不包含 1,我们每碰到一个 0 就把符号 X 压入栈中。 第一个符号 X 代替了初始符号 Z0。当碰到 1 时,我 们就进入状态 p,并且出栈,每输入一个 1 就有一个符号 X 出栈。下推自动机 PDA 是 PN=(q,p,0,1,X,Z0,q,Z0)。规则如下: 1. (q,0,Z0) = (q,X) 2. (q,0,X) = (q,XX) 3. (q,1,X) = (p,) 4. (p,1,X) = (p,) Convert the grammar to a PDA that accepts the same language by empty stack. G=(V,T,Q,S)是一个 CFG,构造以空栈方式接受的 PDA: P=(q,T,VT,转移函数,q,S) (q,0,1),0,1,A,S,q,S) 其中 定义为: 1. (q,S) = (q,0S1), (q,A) 2. (q,A) = (q,1A0), (q,S), (q,) 3. (q,0,0) = (q,) 4. (q,1,1) = (q,) 第七章 unit productions、useless symbols 、CNF a) Eliminate null productions S 是可空的,所以任意生产式体中的 S 可以消去,也可以保留。因为没有体中只有 S 的产生 式,所以不必引入部分消去的规则。所求结果为 S - ASB | AB A - aAS | aA | a B - SbS | bS | Sb | b | A | bb b) Eliminate unit productions B-A 是仅有的单位产生式。于是用 A 的产生式的体替代该产生式的体 A 即得 S - ASB | AB A - aAS | aA | a B - SbS | bS | Sb | b | aAS | aA | a | bb c) Eliminate any useless symbols in the resulting grammer. 观测可得 A 和 B 都能推导出终结符号串,S 也是,所以没有无用符号。 d) change the grammer into CNF 引入新变元和新产生式 C-a 和 D-b,将新变元替代产生式中的终结符得 S - ASB | AB A - CAS | CA | a B - SDS | DS | SD | b | CAS | CA | a | DD C - a D - b 最后处理长度为 3 的几个产生式, 比如 CAS 出现了两次。 引入新变元 E、 F 和 G 来拆分这些产生式的体部分,于是得到 CNF 文法如下: S - AE | AB A - CF | CA | a B - SG | DS | SD | b | CF | CA | a | DD C - a D - b E - SB F - AS G - DS aibjck | i=1,Design a TM accepting the language. 开始时,在带上给定 0 和 1 的有穷序列,前后都是无穷的空格。交替的,这个 TM 将把一个 0 改成 X,然后把一个 1 改成 Y,直到所有的 0 和 1 都已经匹配了 为止。Design TM for the following language: The set of strings with an equal number of 0s and 1s. TM 转移表如下: state 0 1 B X Y q0 (q2,X,R) (q1,X,R) (qf,B,R) - (q0,Y,R) q1 (q3,Y,L) (q1,1,R) - - (q1,Y,R) q2 (q2,0,R) (q3,Y,L) - - (q2,Y,R) q3 (q3,0,L) (q3,1,L) - (q0,X,R) (q3,Y,L) qf - - - - - 说明:TM 在带上来回反复移动。符号 X 和 Y 用来代替相互抵消的 0 和 1。区 别是:在 X 左边没有不匹配的 0 和 1(因此带头移动从不会越过 X 的左边),而在 Y 的左边有 0 或者 1。 开始时处于状态 q0,TM 寻找 0 或者 1,并记住其状态(看到 1 记 q1,看到 0 记 q2),再将其改为 X。作为一种例外,若 TM 进入状态 q0 时看到空格,则所有的 0 和 1 已经匹配,因此进入状态 qf 输入被接收。处于状态 q1,TM 向右移动,寻找 0。 若找到, 则用 Y 代替 0, TM 进入状态 q3 并开始向左移动寻找 X。 类似地, 在状态 q2 寻找 1 匹配 0。 在状态 q3,TM 向左移动直到找到最右的 X。这时重新进入状态 q0,向右移动 越过 Y 直到看到 0,1 或者空格,循环重新开始。
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号