形式语言与自动机作业参考答案(仅供参考).doc

形式语言与自动机 四、五章部分习题答案
形式语言与自动机作业参考答案（仅供参考）
Ø 第四章
10. 把下列文法变换为无ε生成式、无单生成式和没有无用符号的等价文法：
S →A1 | A2 , A1 →A3 | A4 , A2 →A4 | A5 , A3 →S | b |ε, A4 →S | a，A5 →S | d |ε
解: ⑴ 由算法3，变换为无ε生成式：
N’ = { S, A1,A2,A3,A4,A5 }
G1 = ( { S1,S, A1,A2,A3,A4,A5 } , { a,b,d }, P1 , S1 ) ,其中生成式P1如下：
S1 →ε| S ,
S →A1 | A2 ,
A1 →A3 | A4 ,
A2 →A4 | A5 ,
A3 →S | b ,
A4 →S | a ,
A5 →S | d ,
⑵ 由算法4，消单生成式：
NS1 = { S1,S,A1,A2,A3,A4, A5 } ,
NS = NA1 = NA2 = NA3 = NA4 = NA5 = { S, A1,A2,A3,A4, A5 } ,
运用算法4，则P1变为：
S1 →a | b | d |ε ,
S →a | b | d ,
A1 →a | b | d ,
A2 →a | b | d ,
A3 →a | b | d ,
A4 →a | b | d ,
A5 →a | b | d
⑶ 由算法1和算法2，消除无用符号，得到符合题目要求的等价文法：
G1 = ( { S1 } , { a,b,d } , P1 , S1 ) ，其中生成式P1为：S1 →a | b | d |ε.

11. 设2型文法G = ( { S,A,B,C,D,E,F } , { a,b,c } , P , S ) , 其中P：
S →ASB |ε; A →aAS | a ; B →SBS | A | bb
试将G变换为无ε生成式,无单生成式,没有无用符号的文法,再将其转换为Chomsky范式.
解: ⑴ 由算法3，变换为无ε生成式：
N’ = { S }
由S →ASB得出S →ASB | AB ,
由A →aAS得出A →aAS | aA ,
由B →SBS得出B →SBS | SB | BS |B,
由S∈N’ 得出S1 →ε| S ,
因此无ε的等效文法G1 = ( { S1,S,A,B } , { a,b,d } , P1 , S1 ) ,其中生成式P1如下：
S1 →ε| S ,
S →ASB | AB ,
A →aAS | aA | a,
B →SBS | SB | BS | B| A | bb ,
⑵ 由算法4，消单生成式：
NS1 = { S1,S } , NS = { S } , NA = { A } , NB = { A,B }
由于S →ASB | AB∈P且不是单生成式,故P1中有S1 →ε| ASB | AB ,
同理有 S →ASB | AB , A →aAS | aA | a , B →SBS | SB | BS | aAS | aA | a | bb,
因此生成的无单生成式等效文法为
G1 = ( { S1,S, A,B } , { a,b } , P1 , S1 ) ,其中生成式P1如下：
S1 →ε| ASB | AB ,
S →ASB | AB ,
A →aAS | aA | a ,
B →SBS | SB | BS | aAS | aA | a | bb,
⑶ 由算法1和算法2，消除无用符号(此题没有无用符号);
⑷ 转化为等价的Chomsky范式的文法:
将S1 →ASB变换为 S →AC , C →SB ,
将S →ASB 变换为 S →AC ,
将A →aAS | aA 变换为 A →ED | EA, D →AS , E →a,
将B →SBS | aAS | aA | a | bb , 变换为 B →CS | ED | EA | FF, F →b ,
⑸ 由此得出符合题目要求的等价文法：
G1 = ( { S1,S, A,B,C,D } , { a,b } , P1 , S1 ) ,其中生成式P1如下：
S1 →ε| AC | AB ,
S →AC | AB ,
A →ED | EA | a ,
B →CS | SB | BS | ED | EA | a | FF ,
C →SB ,
D →AS ,
E →a ,
F →b .

15. 将下列文法变换为等价的Greibach范式文法:
⑴ S →DD | a , D →SS | b
解: 将非终结符排序为S,D,S为低位,D为高位,
⑴ 对于D →SS ,用S →DD | a 代入得 D →DDS | aS | b ,
用引理4.2.4,变化为D →aS | b | aSD' | bD' , D’ →DS | DSD’ ,
⑵ 将D生成式代入S生成式得 S →aSD | bD | aSD’D | bD'D | a ,
⑶ 将D生成式代入D’生成式得
D’ →aSS | bS | aSD'S | bD'S | aSS D' | bS D' | aSD'S D' | bD'S D' ,
⑷ 由此得出等价的Greibach范式文法：
G1 = ( { S,D,D’ } , { a,b } , P1 , S ) ,其中生成式P1如下：
S →aSD | bD | aSD’D | bD'D | a ,
D →aS | b | aSD' | bD' ,
D’ →aSS | bS | aSD'S | bD'S | aSS D' | bS D' | aSD'S D' | bD'S D' .

⑵ A1 →A3b | A2a , A2 →A1b | A2A2a | b , A3 →A1a | A3A3b | a
解: ⑴ 转化为等价的Chomsky范式的文法:
A1 →A3A4 | A2A5 ,
A2 →A1A4 | A2A6 | b ,
A3 →A1A5 | A3A7 | a ,
A4 →b ,
A5 →a ,
A6 →A2A5 ,
A7 →A3A4 ,
⑵ 转化为等价的Greibach范式的文法:
将非终结符排序为A1, A2,A3,A4,A5 ,A1为低位A5为高位,
①对于A2 →A1A4 ,用A1 →A3A4 | A2A5代入得A2 →A3A4A4 | A2 A5A4 | A2A6 | b ,
用引理4.2.4,变化为
A2 →A3A4A4 | b | A3A4A4A2’ | bA2’ ,
A2’ →A5A4A2’ | A6A2’ | A5A4 | A6 ,
②对于A3 →A1A5 ,用A1 →A3A4 | A2A5代入得A3 →A3A4A5 | A2A5A5 | A3A7 | a ,
A3生成式右边第一个字符仍是较低位的非终结符,将A2生成式代入A3生成式得
A3 →A3A4 A5 | A3A4A4 A5A5 | b A5A5 | A3A4A4A2’ A5A5 | bA2’A5A5 | A3A7 | a ,
用引理4.2.4,变化为
A3 →b A5A5 | bA2’A5A5 | a | b A5A5A3’ | bA2’A5A5A3’ | aA3’ ,
A3’ →A4A5 | A4A4A5A5 | A4A4A2’A5A5 | A7 | A4A5A3’ | A4A4A5A5A3’ | A4A4A2’A5A5A3’ | A7A3’ ,
③对于A6 →A2A5 ,将A2生成式代入A6生成式得
A6 →A3A4A4A5 | bA5 | A3A4A4A2’A5 | bA2’A5 ,
A6生成式右边第一个字符仍是较低位的非终结符,将A3生成式代入A6生成式得
A6 →bA5A5A4A4A5 | bA2’A5A5A4A4A5 | aA4A4A5 | bA5A5A3’A4A4A5 | bA2’A5A5A3’A4A4A5 | aA3’A4A4A5 | bA5A5A4A4A2’A5 | bA2’A5A5A4A4A2’A5 | aA4A4A2’A5 | bA5A5A3’A4A4A2’A5 | bA2’A5A5A3’A4A4A2’A5 | aA3’A4A4A2’A5 | bA2’A5 | b A5 ,
④对于A7 →A3A4 , 将A3生成式代入A7生成式得
A7 →b A5A5A4 | bA2’A5A5A4 | a A4 | b A5A5A3’A4 | bA2’A5A5A3’A4 | aA3’A4 ,
⑤将A5,A6生成式代入A2’生成式得
A2’ →aA4A2’ | bA5A5A4A4A5A2’ | bA2’A5A5A4A4A5A2’ | aA4A4A5A2’ | bA5A5A3’A4A4A5A2’ | bA2’A5A5A3’A4A4A5A2’ | aA3’A4A4A5A2’ | bA5A5A4A4A2’A5 A2’ | bA2’A5A5A4A4A2’A5A2’ | aA4A4A2’A5A2’ | bA5A5A3’A4A4A2’A5A2’ | bA2’A5A5A3’A4A4A2’A5A2’ | aA3’A4A4A2’A5A2’ | bA2’A5A2’ | b A5A2’ | aA4 | b A5A5A4A4A5 | bA2’A5A5A4A4A5 | aA4A4A5 | bA5A5A3’A4A4A5 | bA2’A5A5A3’A4A4A5 | aA3’A4A4A5 | bA5A5A4A4A2’A5 | bA2’A5A5A4A4A2’A5 | aA4A4A2’A5 | bA5A5A3’A4A4A2’A5 | bA2’A5A5A3’A4A4A2’A5 | aA3’A4A4A2’A5 | bA2’A5 | b A5 ,
将A4,A7生成式代入A3’生成式得
A3’ →aA5 | aA4A5A5 | aA4A2’A5A5 | aA5A3’ | aA4A5A5A3’ | aA4A2’A5A5A3’ | b A5A5A4 | bA2’A5A5A4 | aA4 | bA5A5A3’A4 | bA2’A5A5A3’A4 | aA3’A4 | bA5A5A4A3’ | bA2’A5A5A4A3’ | a A4A3’ | b A5A5A3’A4 A3’ | bA2’A5A5A3’A4 A3’ | aA3’A4A3’ ,
⑶ 由此得出等价的Greibach范式文法:
G1 = ( { S,D,D’ } , { a,b } , P1 , S ) ,其中生成式P1如下：
A1 →A3A4 | A2A5 ,
A2 →A3A4A4 | b | A3A4A4A2’ | bA2’ ,
A3 →b A5A5 | bA2’A5A5 | a | bA5A5A3’ | bA2’A5A5A3’ | aA3’ ,
A4 →b ,
A5 →a ,
A6 →bA5A5A4A4A5 | bA2’A5A5A4A4A5 | aA4A4A5 | bA5A5A3’A4A4A5 | bA2’A5A5A3’A4A4A5 | aA3’A4A4A5 | bA5A5A4A4A2’A5 | bA2’A5A5A4A4A2’A5 | aA4A4A2’A5 | bA5A5A3’A4A4A2’A5 | bA2’A5A5A3’A4A4A2’A5 | aA3’A4A4A2’A5 | bA2’A5 | b A5 ,
A7 →b A5A5A4 | bA2’A5A5A4 | a A4 | b A5A5A3’A4 | bA2’A5A5A3’A4 | aA3’A4 ,
A2’ →aA4A2’ | bA5A5A4A4A5A2’ | bA2’A5A5A4A4A5A2’ | aA4A4A5A2’ | bA5A5A3’A4A4A5A2’ | bA2’A5A5A3’A4A4A5A2’ | aA3’A4A4A5A2’ | bA5A5A4A4A2’A5 A2’ | bA2’A5A5A4A4A2’A5A2’ | aA4A4A2’A5A2’ | bA5A5A3’A4A4A2’A5A2’ | bA2’A5A5A3’A4A4A2’A5A2’ | aA3’A4A4A2’A5A2’ | bA2’A5A2’ | bA5A2’ | aA4 | b A5A5A4A4A5 | bA2’A5A5A4A4A5 | aA4A4A5 | bA5A5A3’A4A4A5 | bA2’A5A5A3’A4A4A5 | aA3’A4A4A5 | bA5A5A4A4A2’A5 | bA2’A5A5A4A4A2’A5 | aA4A4A2’A5 | bA5A5A3’A4A4A2’A5 | bA2’A5A5A3’A4A4A2’A5 | aA3’A4A4A2’A5 | bA2’A5 | b A5 ,
A3’ →aA5 | aA4A5A5 | aA4A2’A5A5 | aA5A3’ | aA4A5A5A3’ | aA4A2’A5A5A3’ | b A5A5A4 | bA2’A5A5A4 | aA4 | bA5A5A3’A4 | bA2’A5A5A3’A4 | aA3’A4 | bA5A5A4A3’ | bA2’A5A5A4A3’ | a A4 A3’ | b A5A5A3’A4 A3’ | bA2’A5A5A3’A4 A3’ | aA3’A4A3’ .

20. 设文法G有如下得生成式: S →aDD , D →aS | bS | a , 构造等价的下推自动机.
解: 根据P162-163的算法,构造下推自动机M,使M按文法G的最左推导方式工作.
设M = (Q,T,Г,δ,q0,Z0,F ),其中
Q = { q0,qf } ,
T = { a,b} ,
Г = { a,b,D,S } ,
Z0 = S ,
F = { qf } ,
δ定义如下:
δ( q0,ε,S ) = { ( q0, aDD ) } ,
δ( q0,ε,D ) = { ( q0,aS ) , ( q0,bS ) , ( q0,a ) } ,
δ( q0,a,a ) = { ( q0,ε ) } ,
δ( q0,ε,ε ) = { ( qf,ε ) } .

21. 给出产生语言 L = { aibjck | i , j , k≥0 且 i = j 或者 j = k }的上下文无关文法.你给出的文法是否具有二义性?为什么?
解: G=({S,A,B,C,D,E},{a,b,c}，P，S)
P：S →AD |EB, A →aAb |ε, B →bBc |ε, D →cD |ε, E →aE |ε
文法具有二义性。
因为当句子ω中a,b,c个数相同时，对于ω存在两个不同的最左(右)推导。
如abcÎL，存在两个不同的最左推导 SÞADÞaAbDÞabDÞabcCÞabc 及SÞEBÞaEBÞaBÞabBcÞabc 。

22. 设下推自动机 M = ( {q0,q1},{a,b},{Z0,X},δ, q0, Z0,φ),其中δ如下:
δ(q0,b, Z0) = {(q0, XZ0)} ,δ(q0,ε, Z0) = {(q0, ε)} ,A
δ(q0,b, X) = {(q0, XX)} , δ(q1,b, X) = {(q1, ε)} ,
δ(q0,b, X) = {(q1, X)} , δ(q1,a, Z0) = {(q0, Z0)} ,
试构造文法G产生的语言 L (G) = L(M).
解: 在G中,N = { [q0,Z0,q0], [q0,Z0,q1], [q0,X,q0], [q0,X,q1], [q1,Z0,q0], [q1,Z0,q1], [q1,X,q0], [q1,X,q1] } .
⑴ S生成式有
S →[q0,Z0,q0] ,
S →[q0,Z0,q1] ,
根据δ(q0,b, Z0) = {(q0, XZ0)} ,则有
[q0,Z0,q0] →b[q0,X,q0] [q0,Z0,q0] ,
[q0,Z0,q0] →b[q0,X,q1] [q1,Z0,q0] ,
[q0,Z0,q1] →b[q0,X,q0] [q0,Z0,q1] ,
[q0,Z0,q1] →b[q0,X,q1] [q1,Z0,q1] ,
因为有δ(q0,b, X) = {(q0, XX)},则有
[q0,X,q0] →b[q0,X,q0] [q0,X,q0] ,
[q0, X,q0] →b[q0,X,q1] [q1, X,q0] ,
[q0, X,q1] →b[q0,X,q0] [q0, X,q1] ,
[q0, X,q1] →b[q0,X,q1] [q1, X,q1] ,
因为有δ(q0,a, X) = {(q1, X)},则有
[q0,X,q0] →a[q1,X,q0] ,
[q0,X,q1] →a[q1,X,q1] ,
因为有δ(q1,a, Z0) = {(q0, Z0)},则有
[q1,Z0,q0] →a[q0,Z0,q0] ,
[q1,Z0,q1] →a[q0,Z0,q1] ,
因为有δ(q0,ε, Z0) = {(q0, ε)},则有
[q0,Z0,q0] →ε,
因为有δ(q1,b, X) = {(q1, ε)},则有
[q1,X,q1] →ε
⑵ 利用算法1和算法2,消除无用符号后,得出文法G产生的语言L(G) = { N,T,P,S }
其中N = { S,[q0,Z0,q0],[q1,Z0,q0],[q1,X,q1], [q0,X,q1] },T = { a,b },生成式P如下:
S →[q0,Z0,q0] ,
[q0,Z0,q0] →b[q0,X,q1] [q1,Z0,q0] ,
[q0, X,q1] →b[q0,X,q1] [q1, X,q1] ,
[q0,X,q1] →a[q1,X,q1] ,
[q1,Z0,q0] →a[q0,Z0,q0] ,
[q0,Z0,q0] →ε,
[q0,Z0,q0] →ε.

23. 证明下列语言不是上下文无关语言:
⑴ { anbncm | m≤n };
证明: 假设L是上下文无关语言,由泵浦引理,取常数p,当ω∈L且|ω|≥p时,可取
ω = apbpcp ,将ω写为ω=ω1ω2ω0ω3ω4 ,同时满足|ω2ω0ω3|≤p
⑴ ω2和ω3不可能同时分别包含a和c,因为在这种情况下,有|ω2ω0ω3|>p;
⑵ 如果ω2和ω3都只包含a (b) ,即ω2ω0ω3 = aj (bj ) (j≤p) ,则当i≠1时, ω1ω2iω0ω3iω4中会出现a的个数与b的个数不等;
如果ω2和ω3都只包含c ,即ω2ω0ω3 = cj (j≤p),当i大于1时,ω1ω2iω0ω3iω4中会出现c的个数大于a的个数 (b的个数);
⑶ 如果ω2和ω3分别包含a和b (b和c) ,当i=0时 ω1ω2iω0ω3iω4中会出现a, b的个数小于c的个数（或a,b个数不等）
这些与假设矛盾,故L不是上下文无关语言.
⑵ { ak | k是质数 };
证明: 假设L是上下文无关语言,由泵浦引理,取常数p,当ω∈L且|ω|≥p时,可取ω=ak ( k≥p且k≠1 ) ,将ω写为ω=ω1ω2ω0ω3ω4 ,同时满足|ω2ω0ω3|≤p ,且
|ω2ω3|=j≥1 ,则当i=k+1时,|ω1ω2iω0ω3iω4|=k+(i-1)*j=k+k*j= k*(1+j) ,k*(1+j)至少包含因子k且k≠1 ,因此必定不是质数,即ω1ω2iω0ω3iω4不属于L.
这与假设矛盾,故L不是上下文无关语言.

⑶ 由 a,b,c 组成的字符串且是含有 a,b,c 的个数相同的所有字符串.
证明: 假设L是上下文无关语言,由泵浦引理,取常数p,当ω∈L且|ω|≥p时,可取
ω = akbkck (k≥p) ,将ω写为ω=ω1ω2ω0ω3ω4 ,同时满足|ω2ω0ω3|≤p
⑴ ω2和ω3不可能同时分别包含a和c,因为在这种情况下,有|ω2ω0ω3|>p;
⑵ 如果ω2和ω3都只包含a (b或c) ,即ω2ω0ω3 = aj (bj或cj ) (j≤p) ,则当i≠1时, ω1ω2iω0ω3iω4中会出现a,b,c的个数不再相等;
⑶ 如果ω2和ω3分别包含a和b (b和c) , ω1ω2iω0ω3iω4中会出现a,b的个数与c的不等;
这些与假设矛盾,故L不是上下文无关语言.

24. 设G是Chomsky 范式文法,存在ω∈ L (G) ，求在边缘为ω的推导树中,最长的路径长度与ω的长度之间的关系.
解: 设边缘为ω的推导树中,最长路径长度为n,则它与ω的长度之间的关系为|ω|≤2n-1 .
因为由Chomsky范式的定义可知,Chomsky范式文法的推导树都是二叉树,在最长路径长度为n的二叉推导树中,满二叉树推出的句子长度最长,为2n-1,因此ω的长度与其推导树的最长路径长度n的关系可以用上式表示.

25. 设计PDA接受下列语言(注意:不要求为确定的)
⑴ { 0m1n | m≤n };
解: 设PDA M = ( Q,T,Г,δ,q0,Z0,F ),其中
Q = { q0,q1,qf } ,
T = { 0,1} ,
Г = { 0,1, Z0 } ,
F = { qf } ,
δ定义如下:
δ( q0, ε, Z0 ) = { ( q1, Z0 ) } ,
δ( q0,0, Z0 ) = { ( q0, 0Z0 ) } ,
δ( q0,0,0 ) = { ( q0, 00 ) } ,
δ( q0,1, Z0 ) = { ( qf,ε ) } ,
δ( q0,1, 0 ) = { ( q1,ε ) } ,
δ( q1,1, 0 ) = { ( q1,ε ) } ,
δ( q1,ε, Z0 ) = { ( qf,ε ) }
δ( q1,1, Z0 ) = { ( qf,ε ) }
δ( qf,1, ε) = { ( qf,ε ) }

⑵ { 0m1n | m≥n };
解: 设PDA M = ( Q,T,Г,δ,q0,Z0,F ),其中
Q = { q0,q1,qf } ,
T = { 0,1} ,
Г = { 0,1, Z0 } ,
F = { qf } ,
δ定义如下:
δ( q0, ε, Z0 ) = { ( q1, Z0 ) } ,
δ( q0,0, Z0 ) = { ( q0, 0Z0 ) } ,
δ( q0,0,0 ) = { ( q0, 00 ) } ,
δ( q0,1, 0 ) = { ( q1,ε ) } ,
δ( q1,1, 0 ) = { ( q1,ε ) } ,
δ( q1,ε,Z0 ) = { ( qf,ε ) } ,
δ( q1,ε,0 ) = { ( qf,ε ) }
δ( qf,1, ε) = { ( qf,ε ) }
⑶ { 0m1n0m | n和m任意 };
解: 设PDA M = ( Q,T,Г,δ,q0,Z0,F ),其中
Q = { q0,q1, q2,q3,qf } ,
T = { 0,1} ,
Г = { 0,1, Z0 } ,
F = { qf } ,
δ定义如下:
δ( q0,0, Z0 ) = { ( q0, 0Z0 ) } ,
δ( q0,0,0 ) = { ( q0, 00 ),( q0,ε)} ,
δ( q0,1, Z0 ) = { ( q3,ε ) } ,
δ( q3,1, ε) = { (q3,ε) } ,
δ( q3,ε, ε) = { ( qf,ε ) } ,
δ( q0,1,0 ) = { ( q1,0 ) } ,
δ( q1,1,0 ) = { ( q1,0 ) } ,
δ( q1,0,0 ) = { ( q2,ε ) } ,
δ( q2,0,0 ) = { ( q2,ε ) } ,
δ( q2,ε, Z0 ) = { ( qf,ε ) } ,
δ( q0, ε, Z0 ) = { ( qf, ε)}nm

Ø 第五章
1. 考虑如下的图灵机 M = ( {q0, q1, qf, },{0,1},{0,1,B},δ, q0,B,{ qf } ),其中δ定义为:
δ(q0,0) = {(q1,1,R)} , δ(q1,1) = {(q0,0,R)} , δ(q1,B) = {(qf,B,R)} ,
非形式化但准确地描述该图灵机的工作过程及其所接受的语言.
解: 开始时,M的带上从左端起放有字符串0(10)i (i≥0),后跟无限多个空白符B.M的第一次动作先读到第一个0,并改写为1;然后右移,如果找到第一个1,则改写为0,并继续向右寻找下一个0,这样重复进行.当向右寻找1的时候,找到一个空白符B,则结束.
该图灵机所接受的语言L(M) = { 0(10)i | i≥0 } .
8