形式语言与自动机论文题目

【第一题答案】：令 L1 与 L2 是 context-free languages,而 G1 = (V1, T1, S1, P1) 与 G2 = (V2, T2, S2, P2) 是它们的 context-free grammars,假设 V1 V2 = ,令 G3 = ( V1 V2 {S3}, T1 T2, S3, P3),其中 P3 = P1 P2 {S3 → S1 | S2}.则 L(G3) = L1 L2.令 G4 = ( V1 V2 {S4}, T1 T2, S4, P4), 其中 P4 = P1 P2 {S4 S1S2},则 L(G4) = L(G1)L(G2).令 G5 = ( V1 {S5}, T1, S5, P5), 其中 P5 = P1 {S5 → S1S5 | λ},则 L(G5) = L(G1)*.【第二题答案】：设G=(VT={a,b},VN={S,A,B},S,P}P由下列产生式组成:S→aB|bAA→a|aS|bAA B→b|bS|aBBL(G)={w|w∈{a,b}+,且w中有相同个数的a和b}. 用归纳法证明下面结论(对w的长度) :(1)S w,当且仅当w中含有相同个数的a和b. (2)A w,当且仅当w中a的个数比b的个数多一个. (3)B w,当且仅当w中b的个数比a的个数多一个.归纳基础 当|w|=1,A a, B b, 不能从S导出长度 为1的终极行,则上述结论显然成立.设(1),(2)和(3)对于长度不超过k-1的所有w都成立.那么,证明对|w|=k也成立.对于(1),推导的第一步必是S aB或S bA,对于第一种情形,必有w=aw1且B w1, |w1|=k-1,它含的b个数比a多一个,因此,w中a,b的个数相等.推导的第一步是S bA,证明完全类似.反之,|w|=k, w中a,b的个数相等,要证S w.考虑的S推导,推导出的开始符号,或为a或为b.若S aB,B w1, |w1|=k-1, w1中b的个数比a多一个,w= aw1.若S bA,证明和类S aB类似.

本书以四类形式语言（短语结构语言，上下文有关语言。上下文无关语言。正则语言）和四种自动机（有穷自动机、下推自动机．图灵机，线性有界自动机）为主线，讨论了形式语言与自动机方面的主要理论成果和应用实例。本书的主要特色：取材丰富。涵盖了该领域国内外现有教材的主要内容。在写作方法上，循序渐进，深入浅出。在概念的引入和定理的证明上，尽量采用通俗的语言和形象化的方法来表达。理论与实际相结合。除具有配合定理和定义的大量例题外，许多章节还有现代计算机技术中应用的实例。适应面广。既适合作为本科生的教材，也适合作为研究生的教材。

设计思想： 有两个状态q1和q2：q1是开始状态，q2是终止状态。 栈内符号：A,B,R(R为开始时栈内符号） 开始时，读1，向栈压入A，读0，向栈压入B。 之后：当读1时：如果栈顶是A，再向栈压入一个A 如果栈顶是B，则B退栈 当读0时：如果栈顶是B，再向栈压入一个B 如果栈顶是A，则A退栈