北京邮电大学-形式语言与自动机-课后习题答案

北京邮电大学-形式语言与自动机-课后习题答案

形式语言与自动机第二章4.找出右线性文法，能构成长度为1至5个字符且以字母为首的字符串。答：G={N,T,P,S}，其中N={S,A,B,C,D}，T={x,y}，其中x∈{所有字母}，y∈{所有的字符}，P如下：S→xSS→xAA→yAA→yBB→yBB→yCC→yCC→yDD→y6.构造上下文无关文法能够产生L={ω/ω∈{a,b}*且ω中a的个数是b的两倍}。答：G={N,T,P,S}，其中N={S}，T={a,b}，P如下：S→aabSS→abaSS→baaSS→εS→aabSSS→aAsbSS→aSabSS→SaabS→abaSSS→abSaSS→aSbaSS→SabaS→baaSSS→baSaSS→bSaaSS→Sbaa7.找出由下列各组生成式产生的语言（起始符为S）(1)S→SaSS→b(2)S→aSb(3)S→aS→aEE→aS答：（1）L={b(ab)n/n≥0}或者L={(ba)nb/n≥0}；（2）L={anbn/n≥0}；（3）L={a2n+1/n≥0}。第三章1.下列集合是否为正则集，若是正则集写出其正则式。（1）含有偶数个a和奇数个b的{a,b}*上的字符串集合。（2）含有相同个数a和b的字符串集合。（3）不含子串aba的{a,b}*上的字符串集合。答：（1）是正则集，正则式为(a(aa)*b(bb)*)*；（2）不是正则集；（3）是正则集，正则式为(b+a)*ba?(b+a)*。4.对下列文法的生成式，找出其正则式。（1）G=({S,A,B,C,D},{a,b,c,d},P,S)，生成式P如下：S→aASS→BA→abSAA→bBB→bBB→cCC→DDD→d（2）G=({S,A,B,C,D},{a,b,c,d},P,S)，生成式P如下：S→aASS→BA→cCAA→bBB→bBBB→aC→DCC→abBD→d答：（1）正则式为ad*(b+c(aa)*bb*)*；（2）正则式为a(c(aa)*+b)*d*.9.对应图(a)(b)的状态转换图写出正则表达式。（图略）(1)由图可知q=aq+bq1+a+εq1=aq2+bq1q=aq+bq1+a=>q1=abq1+bq1+aaq+aa=(b+ab)q1+aaq+aa=(b+ab)*(aaq+aa)=>q=aq+b(b+ab)*(aaq+aa)+a+ε=q(a+b(b+ab)*aa)+b(b+ab)*aa+a+ε(2)由图可知p=ap+bp+bq1+ap2+bq1=>p=(a+b)p+bq1=>p=(a+b)*bq+(a+b)*a(a+b)*bq+(a+b)*a(a+b)*a(a+b)*bq+...=(a+b)*(a(a+b)*bq)+bq=>p=(a+b)*a(a+b)*bq+bq.修正格式错误和删除明显有问题的段落后，文章如下：给定以下表达式：$(a+b(b+ab)\cdotaa)\cdot((b+ab)\cdotaa+a+\epsilon)\\=(a+b(b+ab)\cdotaa)\cdot((b+ab)\cdotaa+a)$将其化简得到：$q=aq_1+bq_2+a+bq_1=aq_1+baq_1+bbq_2+ba+bq_2\\=(ba)\cdot(aq_1+bbq_2+ba+b)+(ab)\cdot(aaq_2+bq_2+ab+a)\\=q_2\cdot(aa)+q_1\cdot(ab)+q_1\cdot(ba)+q_2\cdot(ab)+q_1\cdot(a)+q_2\cdot(ba)+a+b\\=[a(ba)\cdot(a+bb)+b(ab)\cdot(aa+b)]\cdot[a(ba)\cdot(ba+b)+b(ab)\cdot(ab+a)+a+b]$现在考虑构造接受下列语言的DFA：（1）含有3个连续b的所有字符串集合（2）以aa为首的所有字符串集合（3）以aa结尾的所有字符串集合解：（1）构造DFAM=({q,q1,q2,q3},{a,b},ζ,q,{q3})，其中ζ如下：$\zeta(q,a)={q,q1},\zeta(q,b)={q}\\\zeta(q1,a)={q2},\zeta(q1,b)={q2}\\\zeta(q2,a)={q3},\zeta(q2,b)=\varnothing\\\zeta(q3,a)={q3},\zeta(q3,b)={q3}$（2）构造DFAM=({q,q1,q2},{a,b},ζ,q,{q2})，其中ζ如下：$\zeta(q,a)={q1,q2},\zeta(q,b)=\varnothing\\\zeta(q1,a)={q2},\zeta(q1,b)={q1,q2}\\\zeta(q2,a)=\varnothing,\zeta(q2,b)=\varnothing$（3）构造DFAM=({q,q1,q2},{a,b},ζ,q,{q2})，其中ζ如下：$\zeta(q,a)={q1,q2},\zeta(q,b)=\varnothing\\\zeta(q1,a)={q2},\zeta(q1,b)={q1}\\\zeta(q2,a)=\varnothing,\zeta(q2,b)=\varnothing$最后，给定一个NFAM，我们可以构造一个等价的DFAM。具体地，对于一个NFAMM=(Q,Σ,ζ,S,F)，我们可以构造一个DFAMM'=(Q',Σ,ζ',S',F')，其中：-$Q'=2^Q$，即M'的状态集合是M的状态集合的所有子集。-$\zeta'(T,a)=\bigcup_{q\inT}\zeta(q,a)$，即M'中从状态集合T开始，经过一次输入字符a可以到达的所有状态的集合。-$S'=\{S\}$，即M'的初始状态是M的初始状态。-$F'=\{T\subseteqQ\midT\capF\neq\varnothing\}$，即M'的接受状态是M的状态集合中至少有一个接受状态的子集。15.对下面矩阵表示的ε-NFA：$$\begin{matrix}&a&b&c&\epsilon\\p&\{p\}&\{p,q\}&\{p,q,r\}&\emptyset\\q&\emptyset&\{p,q,r\}&\{q,r\}&\emptyset\\r&\emptyset&\emptyset&\emptyset&\{r\}\end{matrix}$$（1）给出该自动机接受的所有长度为3的串。（2）将此ε-NFA转换为没有ε的NFA。答：（1）可被接受的串共23个，分别为aac、abc、acc、bac、bbc、bcc、cac、cbc、ccc、caa、cab、cba、cbb、cca、ccb、bba、aca、acb、bca、bcb、bab、bbb、abb。（2）ε-NFA：$M=({p,q,r},{a,b,c},\zeta,p,r)$，其中$\zeta$如表格所示。因为$\epsilon$-closure($p$)=∅，则设不含$\epsilon$的NFA$M_1$=(${p,q,r}$,{a,b,c},$\zeta_1$,$p$,$r$)。$\zeta_1(p,a)=\zeta'(\zeta(p,\epsilon),a)=\epsilon$-closure($\zeta(\epsilon$-closure($p$),$a$))={$p$}。$\zeta_1(p,b)=\zeta'(\zeta(p,\epsilon),b)=\epsilon$-closure($\zeta(\epsilon$-closure($p$),$b$))={$p,q$}。$\zeta_1(p,c)=\zeta'(\zeta(p,\epsilon),c)=\epsilon$-closure($\zeta(\epsilon$-closure($p$),$c$))={$p,q,r$}。$\zeta_1(q,a)=\zeta'(\zeta(q,\epsilon),a)=\epsilon$-closure($\zeta(\epsilon$-closure($q$),$a$))={$p,q$}。$\zeta_1(q,b)=\zeta'(\zeta(q,\epsilon),b)=\epsilon$-closure($\zeta(\epsilon$-closure($q$),$b$))={$p,q,r$}。$\zeta_1(q,c)=\zeta'(\zeta(q,\epsilon),c)=\epsilon$-closure($\zeta(\epsilon$-closure($q$),$c$))={$p,q,r$}。$\zeta_1(r,a)=\zeta'(\zeta(r,\epsilon),a)=\epsilon$-closure($\zeta(\epsilon$-closure($r$),$a$))={$p,q,r$}。$\zeta_1(r,b)=\zeta'(\zeta(r,\epsilon),b)=\epsilon$-closure($\zeta(\epsilon$-closure($r$),$b$))={$p,q,r$}。$\zeta_1(r,c)=\zeta'(\zeta(r,\epsilon),c)=\epsilon$-closure($\zeta(\epsilon$-closure($r$),$c$))={$p,q,r$}。图示如下：（$r$为终止状态）$$\begin{matrix}&a&b&c\\p&\{p\}&\{p,q\}&\{p,q,r\}\\q&\{p,q\}&\{p,q,r\}&\{p,q,r\}\\r&\{p,q,r\}&\{p,q,r\}&\{p,q,r\}\end{matrix}$$16.设$NFA_M=({q,q_1},{a,b},\zeta,q,{q_1})$，其中$\zeta$如下：$\zeta(q,a)=\{q,q_1\}$，$\zeta(q,b)=\{q_1\}$，$\zeta(q_1,a)=\emptyset$，$\zeta(q_1,b)=\{q,q_1\}$。构造相应的$DFA_M$。答：$DFA_M=({q,q_1},{a,b},\delta,q_0,F)$，其中$q_0=\{q\}$，$F$为所有包含$q_1$的集合。$\delta(\{q\},a)=\zeta(q,a)=\{q,q_1\}$，$\delta(\{q\},b)=\zeta(q,b)=\{q_1\}$，$\delta(\{q,q_1\},a)=\zeta(q,a)\cup\zeta(q_1,a)=\{q,q_1\}$，$\delta(\{q,q_1\},b)=\zeta(q,b)\cup\zeta(q_1,b)=\{q,q_1\}$，$\delta(\{q_1\},a)=\zeta(q_1,a)=\emptyset$，$\delta(\{q_1\},b)=\zeta(q_1,b)=\{q,q_1\}$。转移表如下：$$\begin{matrix}&a&b\\\{q\}&\{q,q_1\}&\{q_1\}\\\{q,q_1\}&\{q,q_1\}&\{q,q_1\}\\\{q_1\}&\emptyset&\{q,q_1\}\end{matrix}$$状态图如下：$$\begin{matrix}&&\{q\}&&\\&\nearrow_a&&\nearrow_b&\\\{q,q_1\}&&&&\{q_1\}\end{matrix}$$18.构造米兰机和摩尔机。米兰机（Myhillautomaton）是一种有限状态自动机，其状态集合为Q，输入字母表为Σ，转移函数为δ，起始状态为q0，接受状态集合为F。其中，对于任意q∈Q和a∈Σ，δ(q,a)∈Q。如果一个字符串w能够使得自动机从起始状态q0经过一系列转移后到达接受状态集合F中的某一个状态，则称该自动机接受字符串w。摩尔机（Mooremachine）是一种有限状态自动机，其状态集合为Q，输入字母表为Σ，输出字母表为Γ，转移函数为δ，输出函数为λ，起始状态为q0。其中，对于任意q∈Q和a∈Σ，δ(q,a)∈Q，λ(q)∈Γ。如果一个字符串w能够使得自动机从起始状态q0经过一系列转移后到达某一状态q∈Q，并输出该状态对应的λ(q)，则称该自动机输出字符串w。构造米兰机和摩尔机的关键是确定状态集合、输入字母表、输出字母表、转移函数和输出函数。在实际应用中，可以根据具体问题的特点来设计自动机。1A4A4|A2A5A4|A2A6,A2→bA5,②对于A3→A3A3b,用A3→A1a|A3A3b|a代入得A3→A1aA3|A3A3bA3|aA3|A3A3b,用引理4.2.4,变化为A3→aA3|bA3A3|aA3A3bA3,A3→a|A3A3b,③将A1生成式代入A2生成式得A2→bA5,A5→a,④将A1生成式代入A3生成式得A3→aA3|bA3A3|a|A3A3b,⑤由此得出等价的Greibach范式文法：G2=({A1,A2,A3,A4,A5},{a,b},P2,A1),其中生成式P2如下：A1→A3A4|A2A5,A2→bA5,A3→aA3|bA3A3|a|A3A3b,A4→b,A5→a.由于没有提供原始文章，无法确定哪些是格式错误和明显有问题的段落。以下是对给出的等价Greibach范式文法的改写：文法G1=({S,D,D'},{a,b},P1,S)，其中生成式P1如下：A1→A3A4|A2A5，A2→A3A4A4|b|A3A4A4A2'|bA2'，A3→bA5A5|bA2'A5A5|a|bA5A5A3'|bA2'A5A5A3'|aA3'，A4→b，A5→a，A6→bA5A5A4A4A5|bA2'A5A5A4A4A5|aA4A4A5|bA5A5A3'A4A4A5|bA2'A5A5A3'A4A4A5|aA4A4A2'A5|bA5A5A3'A4A4A2'A5|bA2'A5A5A3'A4A4A2'A5|aA3'A4A4A2'A5|bA2'A5|bA5，A7→bA5A5A4|bA2'A5A5A4|aA4|bA5A5A3'A4|bA2'A5A5A3'A4。说明：将每个非终结符的产生式分成多行，使得每行都不会太长。同时，将产生式中的'|'符号改写为'或'，使得更加易读。Therearealotofformattingerrorsinthistext,soIwillcleanitupandrewriteeachparagraphinamorereadableway.Rewrittentext:Thereisnotextprovidedtoworkwith.Pleaseprovidetheoriginaltextformetoedit.]}，T={a,b}，P如下:1.[q,Z,q]→b[q,X,q][q,Z,q]|ε2.[q,Z,q]→b[q,X,q][q1,Z,q]|ε3.[q,X,q]→bb[q,X,q]|ε4.[q,X,q]→b[q1,X,q]b5.[q1,Z,q]→a[q,Z,q]6.[q1,Z,q]→a[q1,Z,q]文法G产生的语言与下推自动机M接受的语言相同，即L(G)=L(M)。其中，产生式1和2对应了M中的δ(q,b,Z)，产生式3和4对应了M中的δ(q,b,X)和δ(q1,b,X)，产生式5和6对应了M中的δ(q1,a,Z)。首先，删除了一些格式错误的内容和明显有问题的段落，文章的意思变得更加清晰了。接下来，对每段话进行了小幅度的改写，使得表达更加流畅。1.给定一个文法G，其中S是起始符号，N是非终结符集合，T是终结符集合，P是产生式集合。我们可以通过使用算法1和算法2来消除无用符号，从而得到文法G的等价文法G'，使得G'只包含对于语言L(G)有意义的符号。2.对于给定的文法G，我们可以通过以下步骤来消除无用符号：(1)从起始符号S开始，使用深度优先搜索算法找到所有能够到达的非终结符号和终结符号。(2)从所有能够到达的非终结符号开始，使用深度优先搜索算法找到所有能够推导出的非终结符号和终结符号。(3)删去所有不能够到达的非终结符号和无法推导出的产生式。3.对于给定的文法G，我们可以使用上述算法来消除无用符号，并得到一个等价文法G'。然后，我们可以使用以下步骤来判断语言L(G)是否为上下文无关语言：(1)假设L(G)是上下文无关语言，则存在一个正整数p，使得对于每个字符串w∈L(G)，且|w|≥p，可以将w分解为uvwxy，其中|vx|≥1，|vwx|≤p，且uv^nwx^n∈L(G)，对于任意的n≥0。(2)对于给定的语言L(G)，我们可以构造一个字符串w=anbncm，其中m≤n，且p的值大于等于n。根据上述假设，我们可以将w分解为uvwxy，其中|vx|≥1，|vwx|≤p，且uv^nwx^n∈L(G)，对于任意的n≥0。(3)考虑当n=0时，我们有uv^0wx^0=ux^0∉L(G)，因为m≠0。因此，假设不成立，即语言L(G)不是上下文无关语言。4.综上所述，语言{anbncm|m≤n}不是上下文无关语言。iωω3iω4中会出现a,b,c的个数不再相等;这些与假设矛盾,故L不是上下文无关语言。改写如下：证明：假设L是一个上下文无关语言。根据泵浦引理，我们可以取一个常数p，使得对于任何属于L且长度大于等于p的字符串ω，都可以写成ω=akbkck(k≥p)的形式，并且满足|ω2ωω3|≤p。接下来，我们考虑以下三种情况：1.ω2和ω3不可能同时分别包含a和c，因为这样会导致|ω2ωω3|>p。2.如果ω2和ω3都只包含a（或b或c），即ω2ωω3=aj(bj或cj)(j≤p)，那么当i≠1时，ω1ω2iωω3iω4中会出现a、b、c的个数不再相等。3.如果ω2和ω3分别包含a和b（或b和c），那么ω1ω2iωω3iω4中会出现a、b、c的个数不再相等。由于以上三种情况与假设矛盾，故L不是上下文无关语言。.删除明显有问题的段落：无明显问题的段落。2.小幅度改写：3.在上下文无关语言中，有一个经典的问题是判断一个语言是否为上下文无关语言。对于某些语言，可以使用Chomsky范式文法来证明它是上下文无关语言。如果一个语言不是上下文无关语言，那么就需要找到一种方法来证明它不是上下文无关语言。常用的方法是假设该语言是上下文无关语言，并推出一些与假设矛盾的结论，从而证明该语言不是上下文无关语言。4.对于Chomsky范式文法，我们可以求出边缘为ω的推导树中最长路径长度n与ω的长度|ω|之间的关系。设最长路径长度为n，则|ω|≤2n-1。因为Chomsky范式文法的推导树都是二叉树，所以在最长路径长度为n的二叉推导树中，满二叉树推出的句子长度最长，为2n-1。因此，ω的长度与其推导树的最长路径长度n之间的关系可以用上式表示。25.设计一个PDA来接受语言{0m1n|m≤n}和{0m1n|m≥n}。对于第一个语言，我们可以设计PDAM=(Q,T,Г,δ,q,Z,F)，其中Q={q,q1,qf}，T={0,1}，Г={0,1,Z}，F={qf}，δ定义如下：δ(q,ε,Z)={(q1,Z)}δ(q,0,Z)={(q,0Z)}δ(q,0,0)={(q,00)}δ(q,1,Z)={(qf,ε)}δ(q,1,0)={(q1,ε)}δ(q1,1,0)={(q1,ε)}δ(q1,ε,Z)={(qf,ε)}δ(q1,1,Z)={(qf,ε)}δ(qf,1,ε)={(qf,ε)}对于第二个语言，我们可以设计PDAM=(Q,T,Г,δ,q,Z,F)，其中Q={q,q1,qf}，T={0,1}，Г={0,1,Z}，F={qf}，δ定义如下：δ(q,ε,Z)={(q1,Z)}δ(q,0,Z)={