自动机习题答案(0)

1．给出接受下列在字母表{0,1}上的语言的确定型有限自动机（DFA）图书P36 （1） 所有倒过来解释成二进制整数时是3的倍数的串的集合。

q0——对应倒过来除以3余数为0的x组成的等价类； q1——对应倒过来除以3余数为1的x组成的等价类； q2——对应倒过来除以3余数为2的x组成的等价类； qs——A的开始状态。

(1) qs——在此状态下有δ(qs，0)= q0；δ(qs，1)= q1 。

(2) q0——满足此状态的x有：x=3*n+0，通过q0倒过来可以推导状态。 倒过来计算，当读入0的时候，x=2*(3n+0)，所以，?（q0，0）= q0 当读入1的时候，x=2*(3n+0)+1，所以，?（q0，1）= q1 (3) q1——满足此状态的x有：x=3*n+1，通过q1倒过来可以推导状态。 倒过来计算，当读入0的时候，x=2*(3n+1)，所以，?（q1，0）= q2 当读入1的时候，x=2*(3n+1)+1，所以，?（q1，1）= q0 (4) q2——满足此状态的x有：x=3*n+2，通过q2倒过来可以推导状态。 倒过来计算，当读入0的时候，x=2*(3n+2)，所以，?（q2，0）= q1 当读入1的时候，x=2*(3n+2)+1，所以，?（q2，1）= q2

(2)、0的个数被5整除，1的个数被4整除的二进制整数串的集合。

2．把下列正则表达式转化成带ε转移的NFA，并把该自动机转化成等价的状态最小的DFA。图书P72 （1）(0+1)01 （2）00(0+1)*

带空串的非确定型自动机：

1)

2)

? 0 0 1 ? 0 1 0, 1 1 1 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 ? 确定型自动机：

0

0 1 1

0, 1 0 0

======================================================================

3．证明：（1）语言{0n|n是2的幂}不是正则语言；图书P88 证明：

记此语言为L。反设L是正则的，则泵引理成立。对于泵引理中相应于L的正整数N, 取 w = 0, 其中M＝2，则

w=xyz, |xy|<= N, y≠?且xyiz在L中，i=0,1,2,…. 设xz = 0 p, y = 0 q, 则 xyiz = 0 p+iq?L, i= 0,1,2,… 所以 p+iq = 2Ni, i=1,2,…. 于是 (p+(i+1)q)/(p+iq)≥2,

令 i趋于无穷大，则由以上不等式可得 1≥2，矛盾。 （2）语言{anbnci|i≤n}不是上下文无关语言。图书P195 证明：

记此语言为L。反设L是上下文无关的，则泵引理成立。对于泵引理中相应于L的正整数N, 取 z = aNbNcN, 则z?L且|z| ? N，故

z=uvwxy, |vwx|<= N, vx≠?且uviwxiy?L，i=0,1,2,…. 于是可知vwx最少含一个字母、最多含两个字母。

当vx只含一个字母时，若此字母为a或b, 则uv0wx0y中a与b的个数不相同，因此uv0wx0y?L，矛盾；若此字母为c, 则uv2wx2y中c的个数多于b的个数，因此uvwxy?L，矛盾。

当vx恰含两个字母时，若为a,b, 则uv0wx0y中b的个数少于c的个数，因此uv0wx0y?L，矛盾；若此二字母为b,c, 则uv0wx0y中a与b的个数不相等，因此uv0wx0y?L，矛盾。

所以, L 不是上下文无关的。

============================================================= 4．设计下推自动机以及上下文无关文法来识别或生成下列语言：{anbm|n≤m}。 图书P174

确定型下推自动机：

考虑语言L$={anbm$ | n?m}，即原来L中每个串加上$作为结束标志的语言。以接受状态方式接受L$的DPDA为：

P= ( Q,Σ, ?,? ,q0 ,Z0,F), 其中 Q={ q0 , q1 , q2 }, Σ={a,b,$}, ?= {a,b, Z0}, F= {q2}, 转移函数? 的定义为：

2

2

MN

? (q0,a, Z0)={(q0, aZ0)}, ? (q0,a,a)={(q0, aa)}, // 第一阶段 ? (q0,b, Z0)={(q1, Z0)}, ? (q0,b,a)={(q1, ?)},

? (q1,b,a)={(q1, ?)}, ? (q1,b, Z0)={(q1, Z0)}, // 第二阶段

? (q1, $, Z0) = {(q2, ?)}, ? (q0, $, Z0)={(q2, ?)}, // 转入终结状态

上下文无关文法：

a,Z0/a Z0 a,a/aa b,Z0/ Z0 b,a/?

b,Z0/ Z0 b,a/? $,Z0/ ? $,Z0/ ?

构造一个上下文无关文法G，生成语言

L={ anbm: n?m }。 可以用以下文法产生语言L：

G: S S1 因此构成文法G=（V,T,P,S） S1 a S1b|? 其中：V={S,S1} S1 S1b T={a,b}

P={S S1, S1 a S1b| S1b| b|? }

5．分别设计图灵机M，M接受语言P229 （1）｛0n1n2n|n≥1｝。

思路：最初带上为 0 0…0 1 1…1 2 2…2 B B B ……

可以通过判断0、1、2的个数是否相同：消除一个0、然后消除一个1、最后消除一个2。消除的0用X代替、消除的1用Y代替、消除的2用Z代替。图灵机启动后，经过一段运行，输入带上的符号串一般情况为 X…X0…0 Y…Y1…1Z…Z2…2BB 重复循环。

可能出现的边界情况为：

X…XX…X Y…YY…YZ…Z2…2BB X…XX…XY…Y1…1Z…Z2…2BB X…X0…0 Y…YY…YZ…Z2…2BB