离散数学 第11章形式语言与自动机.doc

第11章 形式语言与自动机简介第11章形式语言与自动机1写出字符串011的全部前缀、后缀和子串。解：前缀：0，01，011，后缀：1，11，011，子串：0，01，011，11，12.以合理的顺序展开下列语言，把它们写成带省略号的列举法表示。(1)ab*，(2)a，b*，(3)a*b*，(4)anb2n|n0。解：（1），ab，abab，ababab， （2），a，b，aa，ab，ba，bb，aaa，aab，aba，abb，（3），a，b，ab，aa，bb，aaa，aab，bbb，abb， （4），abb，aabbbb，3.现有文法GS：SaAb，ABcA，AB，Bidt，B，给出下面几个句子的推导过程。(1)aidtccb (2)ab (3)aidtcidtcidtb解：(1) SaAbaBcAbaidtcAbaidtcBcAbaidtccAbaidtccBbaidtccb(2)SaAbaBbab(3) SaAbaBcAbaidtcAbaidtcBcAbaidtcidtcAbaidtcidtcBbaidtcidtcidtb4.指出G(S，a，b，P，S)属于哪一型文法，其中PSbSS，Sa，并用集合的形式写出它产生的语言。解：该文法属于上下文无关文法。以b开头以aa结尾且字符a的个数比字符b的个数多1的所有符号串 5.设M(p，q，r，a，b，p，r)为有限自动机，其中如表11-1所示，画出M的状态转换图，并用格局转换推导式证明字符串abaabL(M)。表11-1状态输入ABpqrqrrPpr解：M的状态转换图如图11-1所示：(p,abaab)(q,baab)(p,aab)(q,ab)(r,b)(r,) 其中rF，即(r,)是终止格局6.设有一个NFA：M=(p，q，r，S，0，1，p，S)，其中状态转换函数如表11-2所示，试构造与它等价的DFA。表11-2状态输入01pqrSp，qrSSprS解: DFA如表11-3所示：表11-3状态输入01pp，qp，q，rp，rp，q，r，Sp，q， Sp，r，Sp， Sp，qp，q，rp，q，r，Sp，q，Sp，q，r，Sp，q，r，Sp，q，Sp，q，Spp，rp，rpp，r，Sp，r，Sp， Sp， S7.已给文法GS：SaAcB，SBdS，BaScA，BcAB，ABaB，AaBc，Aa，Bb，给出下面句子的最左推导、最右推导和相应的导出树。w=(bd)2(ab)2c2ab解：(1) 最左推导: SBdSbdSbdBdS(bd)2S(bd)2 aAcB(bd)2aBaBcB(bd)2abaBcB(bd)2ababcB(bd)2ababc2AB(bd)2ababc2aB(bd)2(ab)2c2ab(2) 最右推导: SBdSBdBdSBdBdaAcBBdBdaAc2ABBdBdaAc2AbBdBdaAc2abBdBda BaB c2abBdBdaBabc2abBdBd(ab)2c2abBdbd(ab)2c2ab(bd)2(ab)2c2ab(3)相应的导出树如图11-1所示： 8.构造一个接受语言L0n1nn1的图灵机。解：识别过程如下：开始时输入带上的符号序列为0n1n。M把最左的0替换成X，读写头右移到最左的1，将之替换成Y。然后左移找到最右的X，右移一格找到最左的0，重复前面的循环。如果当寻找1时M找到的却是空白，M停机拒绝；而当M把一个1替换成Y后，却再也找不到0，则检查有无剩余的1，若没有则接受。综上所述，M(Q，q0，B，F)为所求的图灵机(识别器)，其中Qq0，q1，q2，q3，q4，0，1，0，1，X，Y，B，Fq4，由表11-4给出：表11-401XYBq0(q1，X，R)