形式语言与自动机导论经典复习题

Homework

1.Construct a DFA equivalent to the NFA below.Present the resulting DFA by its state-transition diagram.

E 'E E d d d W c ¨'¨?q 0q 3q 1q 2q 410110ε

ε012.Let Σbe an alphabet and F a ?nite set of (forbidden)strings over Σ.Let L be the language of all strings that do not contain an occurrence of any forbidden string as a substring.Prove that L is regular.

3.The shu?e of two languages L 1and L 2is de?ned as S (L 1,L 2)={w 1u 1w 2u 2···w m u m :w 1w 2···w m ∈L 1,u 1u 2···u m ∈L 2,for all w i ,u i ∈Σ?}.Show that the family of regular languages is closed under the shu?e operation.

4.Find context-free grammar for the following language (with m ≥0,n ≥0,k ≥0)

L ={a n b m c k :n =m or k =m }.

5.Let G =(V,T,S,P )be the grammar described by the following pro-ductions.

S →F B |CA |DE A →SC B →DE |a C →ED |b

D →DD |a

E →EE |S

F |b F →BS

Use the CYK algorithm to determine whether strings babbbb and abaab are in L (G ).For each string,present the ?nal CYK table,and state whether the string is in L (G ).

6.Show that the following language on Σ={a,b,c }is not context-free:

L ={w ∈{a,b,c }?:n a (w )=n b (w )×n c (w )}.

1

where n a(w),n b(w),n c(w)are the numbers of a’s,b’s,c’s occurring in w,respectively.

7.Is the language L={wcw R:w∈{a,b}?}deterministic?While the

language L is deterministic,the closely related language L1={ww R: w∈{a,b}?}is known to be nondeterministic,Give arguments that make this statement plausible.

8.Give a Turing Machine that accepts string over{0,1}whose every pre-

?x(exceptε)has more0’s than1’s.Show how this machine computes on input00101.

9.Show that the language L={a n:n is not a prime number}is a

context-sensitive language.

10.Let M be a string that describes a Turing machine M,and L be the

language{ M :M is Turing machine and L(M)=Σ?}.Show that L is recursively enumerable or not.

2

形式语言与自动机

形式语言与自动机的发展和在计算理论中的作用 2015060104020王桢 形式语言是语言学衍生过来的，开始形式语言并没有用于研究计算机编程语言，而只是研究自然语言的结构。在电子计算机出现以后，人们就马上想到用计算机来作自然语言的机械翻译。可是这项工作并没有所成果，对自然语言的结构 理解太片面化，翻译质量不理想也很难提高。1956年，乔姆斯基发表了用形 式语言方法研究自然语言的第一篇文章。他对语言进行定义：给定一组符号，称 为字母表，用∑表示。又用∑*表示∑中字母组成的所有符号串的集合。∑*的每个子集都是∑上的一个语言。乔姆斯基的语言定义方法为人们所公认，一直沿用下来，乔姆斯基根据文法将语言分成3大类。同时克林在研究神经细跑中，建立 了识别语言的系统有穷状态自动机。乔姆斯基发现自动机和文法分别从生成和识别去表达语言，并建立了形式文法和自动机之间的联系，证明语言的形式文法与自动机之间存在着如下的对应关系：①若某一语言能用图灵机来识别，则它就能 用O型文法生成，反之亦然；②若某一语言能用线性有界自动机来识别，则它 就能用上下文敏感文法生成，反之亦然；③若某一语言能用后进先出自动机来识别，则它就能用上下文自由文法生成，反之亦然；④若某一语言能用有限自动机来识别，则它就能用有限状态文法生成，反之亦然。这一成果将形式语言引入数 学，使得形式语言真正诞生。1960年，算法语言ALGOL60报告发表。1961年，又发表了ALGOL60修改报告。在这两个报告中，第一次使用一种称为BNF 范式的形式方法来描述程序设计语言ALGOL60的语法。不久，人们即发现BNF 范式极其类似于形式语言理论中的上下文无关文法，从而打开了形式语言广泛应用于程序设计语言的局面，并给形式语言理论本身的研究以极大的推动，使它发展成为理论计算机科学的一个重要分支。 形式语言理论是从语言学衍生而来，作为一种理解自然语言的句法规律。在发展过程中人们发现其在计算机语言中的作用，计算机语言在计算机科学中，形式语言通常作为定义编程语言和语法的基础。对编程语言编译，使之转换成机器语言，形式语言在这一工作中有很重要的作用。形式语言推动了计算机学科的发展，并成为计算机学科里重要的分支。 19世纪中，布尔用数学方法研究思维规律的问题建立了逻辑代数，即布尔代数。肖斯塔科夫和仙农，独立地应用布尔代数于继电器接点电路的分析和综合,

《形式语言与自动机》(王柏、杨娟编著)课后习题答案

形式语言与自动机课后习题答案 第二章 4．找出右线性文法，能构成长度为1至5个字符且以字母为首的字符串。 答：G={N,T,P,S} 其中N={S,A,B,C,D} T={x,y} 其中x ∈{所有字母} y ∈{所有的字符} P 如下: S →x S →xA A →y A →yB B →y B →y C C →y C →y D D →y 6．构造上下文无关文法能够产生 L={ω/ω∈{a,b}*且ω中a 的个数是b 的两倍} ! 答：G={N,T,P,S} 其中N={S} T={a,b} P 如下: S →aab S →aba S →baa S →aabS S →aaSb S →aSab S →Saab S →abaS S →abSa S →aSba S →Saba S →baaS S →baSa S →bSaa S →Sbaa 7．找出由下列各组生成式产生的语言（起始符为S ） (1) S →SaS S →b (2) S →aSb S →c (3) / (4) S →a S →aE E →aS 答：（1）b(ab)n /n ≥0}或者L={(ba)n b /n ≥0} (2) L={a n cb n /n ≥0} (3) L={a 2n+1 /n ≥0} 第三章 1． 下列集合是否为正则集，若是正则集写出其正则式。 （1） 含有偶数个a 和奇数个b 的{a,b}*上的字符串集合 （2） 含有相同个数a 和b 的字符串集合 （3） < （4） 不含子串aba 的{a,b}*上的字符串集合 答：（1）是正则集，自动机如下 a

a (2) 不是正则集，用泵浦引理可以证明，具体见17题（2）。 (3) 是正则集 先看L’为包含子串aba的{a,b}*上的字符串集合 { 显然这是正则集，可以写出表达式和画出自动机。（略）则不包含子串aba的{a,b}*上的字符串集合L是L’的非。 根据正则集的性质，L也是正则集。 4．对下列文法的生成式，找出其正则式 （1）G=({S,A,B,C,D},{a,b,c,d},P,S),生成式P如下： S→aA S→B A→abS A→bB B→b B→cC C→D D→bB … D→d （2）G=({S,A,B,C,D},{a,b,c,d},P,S),生成式P如下： S→aA S→B A→cC A→bB B→bB B→a C→D C→abB D→d 答：(1) 由生成式得： S=aA+B ① A=abS+bB ② ] B=b+cC ③ C=D ④ D=d+bB ⑤ ③④⑤式化简消去CD，得到B=b+c(d+bB) 即B=cbB+cd+b =>B=(cb)*(cd+b) ⑥ 将②⑥代入① S=aabS+ab(cb)*(cd+b)+(cb)*(cd+b) =>S=(aab)*(ab+ε)(cb)*(cd+b) (2) 由生成式得： S=aA+B ① A=bB+cC ② … B=a+bB ③ C=D+abB ④ D=dB ⑤ 由③得B=b*a ⑥

形式语言与自动机理论试题答案解析

形式语言与自动机理论试题答案解析 一、按要求完成下列填空 1.给出集合{Φ,{Φ}}和集合{ε,0,00}的幂集（2x4'） (1) {Φ,{Φ},{{Φ}},{Φ,{Φ}}} (2) {Φ,{ε},{0},{00},{ε,0},{ε,00},{0,00},{ε,0,00}} 2.设∑={0,1},请给出∑上的下列语言的文法（2x5'） (1)所有包含子串01011的串 S→X01011Y X→ε|0X|1X Y→ε|0Y|1Y (2)所有既没有一对连续的0，也没有一对连续的1的串 A→ε|A’|A” A’→0|01|01A’ A”→1|10|10A” 3.构造识别下列语言的DFA 2x6' (1) {x|x∈{0，1}+且x以0开头以1结尾} （设置陷阱状态，当第一个字符为1时，进入陷阱状态） (2) {x|x∈{0，1}+且x的第十个字符为1} （设置一个陷阱状态，一旦发现x的第十个字符为0，进入陷阱状态）

二、判断（正确的写T ，错误的写F ） 5x2' 1.设1R 和2R 是集合{a,b,c,d,e}上的二元关系，则 3231321)(R R R R R R R I I ? ( T ) 任取(x.,y),其中x,y },,,,{e d c b a ∈，使得321)(),(R R R y x I ∈。 )),(),((321R y z R R z x z ∈∧∈??I },,,,{e d c b a z ∈ )),(),(),((321R y z R z x R z x z ∈∧∈∧∈?? )),(),(()),(),((3231R y z R z x z R y z R z x z ∈∧∈?∧∈∧∈?? 3231),(),(R R y x R R y x ∈∧∈? 3231),(R R R R y x I ∈? 2.对于任一非空集合A ，Φ?A 2 ( T ) 3.文法G ：S A|AS A a|b|c|d|e|f|g 是RG ( F ) 4.3型语言 I 2型语言 I 1型语言 I 0型语言 ( F ) 5.s （rs+s ）*r=rr *s （rr *s ）* ( F ) 不成立，假设r,s 分别是表示语言R ，S 的正则表达式，例如当R={0}，S={1}, L(s(rs+s)*r)是以1开头的字符串，而L(rr*s(rr*s)*)是以0开头的字符串.L(s(rs+s)*r) ≠ L(rr*s(rr*s)*) 所以s(rs+s)*r ≠ rr*s(rr*s)*,结论不成立 三、设文法G 的产生式集如下，试给出句子aaabbbccc 的至少两个不同的推导（12分）。 aSBC aBC S |→ ab aB → bB →bb CB →BC bC →bc cC →cc

形式语言与自动机理论蒋宗礼第三章参考答案

第三章作业答案 1．已知DFA M1与M2如图3－18所示。 (敖雪峰 02282068) (1) 请分别给出它们在处理字符串1011001的过程中经过的状态序列。 (2) 请给出它们的形式描述。 S q q 1 图3－18 两个不同的DFA 解答：(1)M1在处理1011001的过程中经过的状态序列为q 0q 3q 1q 3q 2q 3q 1q 3; M2在处理1011001的过程中经过的状态序列为q 0q 2q 3q 1q 3q 2q 3q 1; (2)考虑到用形式语言表示,用自然语言似乎不是那么容易,所以用图上作业法把它们用正则表达式来描述: M1: [01+(00+1)(11+0)][11+(10+0)(11+0)]* M2: (01+1+000){(01)*+[(001+11)(01+1+000)]*} ******************************************************************************* 2．构造下列语言的DFA ( 陶文婧 02282085 ) （1）{0，1}* ，1 （2）{0 ，1}+ ，1 （3）{x|x {0，1}+且x 中不含00的串} （设置一个陷阱状态，一旦发现有00的子串，就进入陷阱状态）

（4）{ x|x∈{0，1}*且x中不含00的串} （可接受空字符串，所以初始状态也是接受状态） （5）{x|x∈{0，1}+且x中含形如10110的子串} （6）{x|x∈{0，1}+且x中不含形如10110的子串} （设置一个陷阱状态，一旦发现有00的子串，就进入陷阱状态） （7）{x|x∈{0，1}+且当把x看成二进制时，x模5和3同余，要求当x为0时，|x|=1,且x≠0时，x的首字符为1 } 1.以0开头的串不被接受，故设置陷阱状态，当DFA在启动状态读入的符号为0，则进 入陷阱状态 2.设置7个状态：开始状态q s,q0:除以5余0的等价类，q1：除以5余1的等价类,q2:除以5 余2的等价类，q3:除以5余3的等价类，q4:除以5余4的等价类，接受状态q t

形式语言与自动机课后习题答案

形式语言与自动机课后作业答案 第二章 4．找出右线性文法，能构成长度为1至5个字符且以字母为首的字符串。 答：G={N,T,P,S} 其中N={S,A,B,C,D} T={x,y} 其中x∈{所有字母} y∈{所有的字符} P如下: S→x S→xA A→y A→yB B→y B→yC C→y C→yD D→y 6．构造上下文无关文法能够产生 L={ω/ω∈{a,b}*且ω中a的个数是b的两倍} 答：G={N,T,P,S} 其中N={S} T={a,b} P如下: S→aab S→aba S→baa S→aabS S→aaSb S→aSab S→Saab S→abaS S→abSa S→aSba S→Saba S→baaS S→baSa S→bSaa S→Sbaa 7．找出由下列各组生成式产生的语言（起始符为S） (1)S→SaS S→b (2)S→aSb S→c (3)S→a S→aE E→aS 答：（1）b(ab)n /n≥0}或者L={(ba)n b/n≥0} (2) L={a n cb n /n≥0} (3)L={a2n+1 /n≥0} 第三章 1．下列集合是否为正则集，若是正则集写出其正则式。 （1）含有偶数个a和奇数个b的{a,b}*上的字符串集合 （2）含有相同个数a和b的字符串集合 （3）不含子串aba的{a,b}*上的字符串集合 答：（1）是正则集，自动机如下 (2) 不是正则集，用泵浦引理可以证明，具体见17题（2）。

(3) 是正则集 先看L’为包含子串aba的{a,b}*上的字符串集合 显然这是正则集，可以写出表达式和画出自动机。（略） 则不包含子串aba的{a,b}*上的字符串集合L是L’的非。 根据正则集的性质，L也是正则集。 4．对下列文法的生成式，找出其正则式 （1）G=({S,A,B,C,D},{a,b,c,d},P,S),生成式P如下： S→aA S→B A→abS A→bB B→b B→cC C→D D→bB D→d （2）G=({S,A,B,C,D},{a,b,c,d},P,S),生成式P如下： S→aA S→B A→cC A→bB B→bB B→a C→D C→abB D→d 答：(1) 由生成式得： S=aA+B ① A=abS+bB ② B=b+cC ③ C=D ④ D=d+bB ⑤ ③④⑤式化简消去CD，得到B=b+c(d+bB) 即B=cbB+cd+b =>B=(cb)*(cd+b) ⑥ 将②⑥代入① S=aabS+ab(cb)*(cd+b)+(cb)*(cd+b) =>S=(aab)*(ab+ε)(cb)*(cd+b) (2) 由生成式得： S=aA+B ① A=bB+cC ② B=a+bB ③ C=D+abB ④ D=dB ⑤ 由③得 B=b*a ⑥ 将⑤⑥代入④ C=d+abb*a=d+ab+a ⑦ 将⑥⑦代入② A=b+a+c(d+b+a) ⑧ 将⑥⑧代入① S=a(b+a+c(d+ab+a))+b*a =ab+a+acd+acab+a+b*a 5.为下列正则集，构造右线性文法： (1){a,b}* (2)以abb结尾的由a和b组成的所有字符串的集合

形式语言与自动机理论试题答案解析

形式语言与自动机理论试题答案解析 一、按要求完成下列填空 1. 给出集合{Φ,{Φ}}和集合{ε,0,00}的幂集 （2x4'） (1) {Φ,{Φ},{{Φ}},{Φ,{Φ}}} (2) {Φ,{ε},{0},{00},{ε,0},{ε,00},{0,00},{ε,0,00}} 2. 设∑={0,1},请给出∑上的下列语言的文法 （2x5'） (1)所有包含子串01011的串 S →X01011Y X →ε|0X|1X Y →ε|0Y|1Y (2)所有既没有一对连续的0，也没有一对连续的1的串 A →ε |A ’|A ” A’ →0|01|01A ’ A ” →1|10|10A ” 3. 构造识别下列语言的DFA 2x6' (1) {x|x ∈{0，1}+且x 以0开头以1结尾} （设置陷阱状态，当第一个字符为1时，进入陷阱状态） 1 S 1 1 0,10 (2) {x|x ∈{0，1} + 且x 的第十个字符为1} （设置一个陷阱状态，一旦发现x 的第十个字符为0，进入陷阱状态） 1S 0,1 0,10,10,10,110,0,10,10,10,1 0,1

二、判断（正确的写T ，错误的写F ） 5x2' 1.设1R 和2R 是集合{a,b,c,d,e}上的二元关系，则 3231321)(R R R R R R R ? ( T ) 任取(x.,y),其中x,y },,,,{e d c b a ∈，使得321)(),(R R R y x ∈。 )),(),((321R y z R R z x z ∈∧∈?? },,,,{e d c b a z ∈ )),(),(),((321R y z R z x R z x z ∈∧∈∧∈?? )),(),(()),(),((3231R y z R z x z R y z R z x z ∈∧∈?∧∈∧∈?? 3231),(),(R R y x R R y x ∈∧∈? 3231),(R R R R y x ∈? 2.对于任一非空集合A ，Φ?A 2 ( T ) 3.文法G ：S A|AS A a|b|c|d|e|f|g 是RG ( F ) 4.3型语言 2型语言 1型语言 0型语言 ( F ) 5.s （rs+s ）*r=rr *s （rr *s ）* ( F ) 不成立，假设r,s 分别是表示语言R ，S 的正则表达式，例如当R={0}，S={1}, L(s(rs+s)*r)是以1开头的字符串，而L(rr*s(rr*s)*)是以0开头的字符串.L(s(rs+s)*r) ≠ L(rr*s(rr*s)*) 所以s(rs+s)*r ≠ rr*s(rr*s)*,结论不成立 三、设文法G 的产生式集如下，试给出句子aaabbbccc 的至少两个不同的推导（12分）。 aSBC aBC S |→ ab aB → bB →bb CB →BC bC →bc cC →cc

形式语言与自动机的关系

形式语言与自动机的关系研究 新疆师范大学数理信息学院数学03-6班摘要： 形式语言的直观意义，自动机的直观意义，形式语言的定义， 形式语言的特征，语法的分类，自动机的定义，自动机的分 类，各种自动机的定义，形式语言和自动的的关系，自动机 的对语言的例子 基本关键词： 形式语言的定义；自动机的定义；形式语言和自动机的关系 1，形式语言的直观意义 α→的直观地讲，形式语言是用来精确描述语言和它结构的手段。它一重写规则β α,均为字符串。重写规则就是在包含α的字符穿中遇见规则左边的形式来表示，其中，β α时，α部分重新写为右边的β。这样一个初设的字符串通过不断地运用重写规则，就可以到另一个字符串。通过选择不同的规则并且以各种不同的顺序来运用最这些规则，如果指 定一个初始符，某规则以其为左部，一组规则就可以构成一个语法。 2，形式语言的定义

形式语法是一个四元组G=（N, V , P, S ）,其中N 是非终结符的有限集合，有时也称变量，它们相当于各种句法范畴。V 是终结符的有限集合，若语法生成的是自然语言，这些终端语符就相当于这种语言中具体的词，终端 语符集 这种语言的词库，P 是以重写规则的有限集合，基本形式P }{βα→，即""βα改写为，其中箭头表示指令，一条规则就是一个机械性的操作程序，用来演算它联系着的两侧语符集或语符序列之间的关系，而S 是一个特定的初始符； 3，语法的分类 乔姆斯在他的著名【文章】中根据重写规则将语法分成四类：正则语法，上下文有关语法，上下文无关语法；有这些语法生成的语言是正则语言，，上下文有关语言，上下文无关语言，递归数集合。 a 如果P 中的规则，满足如下的形式：x A Bx A →→或，，其中，A,B 是非终结符，x 是终结符，则G 称为正则语法（简称为FSG ）。 b 如果P 中的规则，满足如下的形式：α→A ,其中，A 是非终结符, α是由N 和V 中字符所组成的字符串（或可表示为()*∈V N α,*意味着它右边的字符可以重复0到任何 多次），则G 称为上下文无关语法（简称为CFG ）。 d 如果P 中的规则，满足如下的形式：αγββα→A ,其中，A 是非终结符,γβα,,,是字符串，且γ至少包含一个字符，则G 称为上下有无关语法（简称为CSG ）。 d 如果P 中的规则，满足如下的形式：其中，α，β是字符串，则G 称为无限制重写系统。 对于以上任何一种语法，两个字符串之间一次派生关系?可定义为： 如果y x →是P 中的规则，βαβαy x ?。 字符串α，β有多次派生关系* ?则是说，通过多次应用一次派生关系，从α可派生出β，并记为α* ?β： n αβαα==,0，而对n i i n i +?-=αα,1,....0。 给定以语法，其语言定义为所有合法终结字符串的集合。合法终结字符串是指由初始符S 出发，运用重写规则而派生得终结字符串，即， (){}ααα**;?∈=S V G L 例子：假设G=(N, V , P, S), N={S, A} , V={0, 1}, P={0,0,1→→→A A A A S } 则 ，{}110)(≥=m G L m 是正则语法，在V={0, 1}上它所对应的正则表达式是100*。 形式语言的特征： ⑴ 高度抽象化（采用形式化的手段，专用符号，数学公式来描述语言的，结构关系，这种关系是抽象的）。

形式语言与自动机理论蒋宗礼第一章参考答案

第一章参考答案 1.1请用列举法给出下列集合。（吴贤珺02282047） ⑴你知道的各种颜色。 解：{红，橙，黄，绿，青，蓝，紫} ⑵大学教师中的各种职称。 解：{助教，讲师，副教授，教授} ⑶你所学过的课程。 解：{语文，数学，英语，物理，化学，生物，历史，地理，政治} ⑷你的家庭成员。 解：{父亲，母亲，妹妹，我} ⑸你知道的所有交通工具。 解：{汽车，火车，飞机，轮船，马车} ⑹字母表{a , b}上长度小于4的串的集合。 解：{a,b,aa,bb,ab,ba,aaa,aab,aba,abb,baa,bab,bba,bbb} ⑺集合{1,2,3,4}的幂集。 解：{Φ,{1},{2},{3},{4},{1,2},{1,3},{1,4},{2,3},{2,4},{3,4},{1,2,3},{1,2,4}, {1,3,4},{2,3,4},{1,2,3,4} } ⑻所有的非负奇数。 解：{1,3,5,7,…} ⑼0～100的所有正整数。 解：{1,2,3, (100) (10) 1～10之间的和为10的整数集合的集合。 解：设所求的集合为A，集合A中的元素为A i（i=1,2,3,…），A i也是集合，A i中的元素在1～10之间，并且和为10。根据集合元素的彼此可区分性，可以计算出A i中元素的最多个数，方法是：把1开始的正整数逐个相加，直到等于10（即10=1+2+3+4），这样， A i中最多有4个元素。原因是：从最小的1开始，每次加入新的元素都只依次增加1， 这样相加的和最小，要加到10，元素个数就最多。 求出最大的∣A i∣＝4后，再求出元素个数为3，2，1的集合就可以了。 故A={{10},{1,9},{2,8},{3,7},{4,6},{1,2,7},{1,3,6},{1,4,5},{2,3,5},{1,2,3,4}} 1.2 请用命题法给出下列集合

形式语言与自动机理论试题

形式语言与自动机理论试题 、按要求完成下列填空 1. 给出集合{①,{①}}和集合{￡ ,0,00}的幕集 (2x4') ⑴{①，{①}，{{①}}，{①，{①}}} (2) {①,{ ￡ },{0},{00},{ ￡,0},{ ￡,00},{0,00},{ ￡ ,0,00}} 2. 设刀={0,1},请给出刀上的下列语言的文法(2x5') (1) 所有包含子串01011的串 S T X01011Y Xr |0X|1X Yf |0Y|1Y (2) 所有既没有一对连续的0,也没有一对连续的1的串 A T￡ |A ' ” A T0|01|01A ' A T 1|10|10A ” 3. 构造识别下列语言的DFA 2x6' (1) {x|x {0, 1}+且x以0开头以1结尾} (设置陷阱状态，当第一个字符为1时，进入陷阱状态) (2) {x|x {0, 1}+且x的第十个字符为1} (设置一个陷阱状态，一旦发现x的第十个字符为0，进入陷阱状态) 0,1

、判断(正确的写 T ,错误的写F ) 5x2 1?设R 和R 2是集合{a,b,c,d,e}上的二元关系，则 (R 只2 )民 R R 只只 (T ) 任取(x.,y),其中 x,y {a,b,c,d,e}，使得(x,y) (R R 2)FR 。 不成立，假设r,s 分别是表示语言 R, S 的正则表达式，例如当R={0}, S={1}, L(s(rs+s)*r) 是以1开头的字符串，而 L(rr*s(rr*s)*)是以0开头的字符串.L(s(rs+s)*r) L(rr*s(rr*s)*) 所以s(rs+s)*r rr*s(rr*s)*,结论不成立 、设文法G 的产生式集如下，试给出句子 aaabbbccc 的至少两个不同的推导(12分)。 S aBC|aSBC aB ab bB T bb CB T BC bC T bc C C T cc 推导一： S=>aSBC =>aaSBCBC =>aaaBCBCBC =>aaabCBCBC =>aaabBCCBC =>aaabbCCBC =>aaabbCBCC z((x, z) R R 2 (z, y) R 3) z {a,b,c,d,e} z((x, z) R 1 (x, z ) R 2 (z, y) R 3) z((x,z) R 1 (z,y) R a ) z((x,z) R 2 (z, y) (x,y) R 1 R 3 (x, y) R 2R 3 (x, y) R 1 R 3 R 2 R 3 2.对于任 ?非空集合A , ①2A (T ) 3.文法G : S f A|AS A —? a|b|c|d|e|f|g 是 RG (F) 型语言 2型语言 1型语言 0型语言 (T ) * (rs+s ) * * r=rr s (rr s ) * (F ) R a )

《形式语言与自动机》(王柏、杨娟编著)北邮出版社_课后习题答案

北京邮电大学——形式语言与自动机课后作业答案 第二章 4．找出右线性文法，能构成长度为1至5个字符且以字母为首的字符串。 答：G={N,T,P,S} 其中N={S,A,B,C,D} T={x,y} 其中x∈{所有字母} y∈{所有的字符} P如下: S→x S→xA A→y A→yB B→y B→yC C→y C→yD D→y 6．构造上下文无关文法能够产生 L={ω/ω∈{a,b}*且ω中a的个数是b的两倍} 答：G={N,T,P,S} 其中N={S} T={a,b} P如下: S→aab S→aba S→baa S→aabS S→aaSb S→aSab S→Saab S→abaS S→abSa S→aSba S→Saba S→baaS S→baSa S→bSaa S→Sbaa 7．找出由下列各组生成式产生的语言（起始符为S） (1)S→SaS S→b (2)S→aSb S→c (3)S→a S→aE E→aS 答：（1）b(ab)n /n≥0}或者L={(ba)n b/n≥0} (2) L={a n cb n /n≥0} (3)L={a2n+1 /n≥0} 第三章 1．下列集合是否为正则集，若是正则集写出其正则式。 （1）含有偶数个a和奇数个b的{a,b}*上的字符串集合 （2）含有相同个数a和b的字符串集合 （3）不含子串aba的{a,b}*上的字符串集合 答：（1）是正则集，自动机如下 (2) 不是正则集，用泵浦引理可以证明，具体见17题（2）。

(3) 是正则集 先看L’为包含子串aba的{a,b}*上的字符串集合 显然这是正则集，可以写出表达式和画出自动机。（略） 则不包含子串aba的{a,b}*上的字符串集合L是L’的非。 根据正则集的性质，L也是正则集。 4．对下列文法的生成式，找出其正则式 （1）G=({S,A,B,C,D},{a,b,c,d},P,S),生成式P如下： S→aA S→B A→abS A→bB B→b B→cC C→D D→bB D→d （2）G=({S,A,B,C,D},{a,b,c,d},P,S),生成式P如下： S→aA S→B A→cC A→bB B→bB B→a C→D C→abB D→d 答：(1) 由生成式得： S=aA+B ① A=abS+bB ② B=b+cC ③ C=D ④ D=d+bB ⑤ ③④⑤式化简消去CD，得到B=b+c(d+bB) 即B=cbB+cd+b =>B=(cb)*(cd+b) ⑥ 将②⑥代入① S=aabS+ab(cb)*(cd+b)+(cb)*(cd+b) =>S=(aab)*(ab+ε)(cb)*(cd+b) (2) 由生成式得： S=aA+B ① A=bB+cC ② B=a+bB ③ C=D+abB ④ D=dB ⑤ 由③得 B=b*a ⑥ 将⑤⑥代入④ C=d+abb*a=d+ab+a ⑦ 将⑥⑦代入② A=b+a+c(d+b+a) ⑧ 将⑥⑧代入① S=a(b+a+c(d+ab+a))+b*a =ab+a+acd+acab+a+b*a 5.为下列正则集，构造右线性文法： (1){a,b}* (2)以abb结尾的由a和b组成的所有字符串的集合

第二章节形式语言与自动机理论参考测试答案

2．1回答下面的问题： （周期律 02282067） （1）在文法中，终极符号和非终极符号各起什么作用？ ? 终结符号是一个文法所产生的语言中句子的中出现的字符，他决定了一个文法的产生语 言中字符的范围。 ? 非终结符号又叫做一个语法变量，它表示一个语法范畴，文法中每一个产生式的左部至 少要还有一个非终结符号，（二，三型文法要求更严，只允许左部为一个非终结符号）他是推导或归约的核心。 （2）文法的语法范畴有什么意义？开始符号所对应的语法范畴有什么特殊意义？ ? 文法的非终结符号A 所对应的语法范畴代表着一个集合L （A ），此集合由文法产生式 中关于A 的产生式推导实现的 ? 开始符号所对应的语法范畴则为文法G = {V ，T ，P ，S}所产生的语言L （G ） ={w S T w w **|?∈且} （3）在文法中，除了的变量可以对应一个终极符号行的集合外，按照类似的对应方法，一个字符串也可以对应一个终极符号行集合，这个集合表达什么意义？ ? 字符串对应的终极符号行集合表示这个字符串所能推导到的终极字符串集合，为某个句 型的语言。 （4）文法中的归约和推导有什么不同？ ? 推导：文法G = {V ，T ，P ，S}，如果,)(,,* T V P ∈∈→δγβα则称γαδ在G 中推导出了γβδ。 ? 归约：文法G = {V ，T ，P ，S}，如果,)(,,* T V P ∈∈→δγβα则称γβδ在G 中归约到γαδ。 ? 这他们的定义，我个人理解两个概念从不同角度看待文法中的产生式，推导是自上而下 （从产生式的左边到右边），而归约是自下而上（从产生式的右边到左边），体现到具体实际中，如编译中语法分析时语法树的建立，递归下降，LL （1）等分析法采用自开始符号向下推导识别输入代码生成语法树，对应的LR （1），LALR 等分析法则是采用自输入代码（相当于文法中语言的句子）自底向上归约到开始符号建立语法树，各有优劣。 （5）为什么要求定义语言的字母表上的语言为一个非空有穷集合？ ? 非空：根据字母表幂的定义：εε,}{0∑=为字母表中０个字符组成的。这样，当字母 表中没有字符的情况，字母表也有一个元素，字母表为空就没有意义，而且，如果字母表为空，将无法定义其上的语言，使得理论体系不严密。 ? 有穷：我们将语言抽象成形式语言的目的就是为了有穷的表示无限的语言，在此基础上 我们才定义了字母表和语言，如果字母表为无穷的，他就违背了我们研究问题的初衷，这也使得研究失去意义

形式语言与自动机论文

关于 《结构化程序设计思想在形式语言与自动机理论中的体现》 一文中性质语言与自动机相关理论知识的分析与感悟 ————戚洪源 摘 要：本文为本科阶段学习形式语言与自动机课程过程中阅读专业文献后，对于该文献中所涉及的形式语言与自动机的专业知识进行解读和分析，以及一些个人在学习形式语言与自动机课程后的感悟。 关键词：形式语言与自动机 结构化程序设计 计算机理论 正 文： 一、关于文献中形式语言与自动机相关知识的解读 （一）文章第二部分涉及到的关于正则文法的相关知识 文章的第二部分：构造文法时结构化思想的体现。在这一部分中，作者举了一个经典的正则文法的例子： MA D M M M M M M M A AM N D P D N B P B N R R R R S →→→→→→→-+→98 (32109) 8...321.0.0 ε 首先我们运用学过的知识将这个文法转化为一个等价的正则文法：

定义2.5 若对于文法G=(V,T,P,S),P 中每个产生式都有如下形式： {}V B A T a aB A a A ∈∈→→,,, ε或 则称G 为正则文法。 在这个文法中，除了第三行、第四行、第五行、第八行，每一个语句都满足正则文法语句的要求。而对于第五行，可以转化为： M M M M M N 98...210→ 第八行可以转化为： 98...32198...210D D D D D D → 第三行的转化为： D B B B B B B .|9|8...3|2|1→ 至于第四行，转化相对复杂一些，我用了如下的方法： 引入新变量E D E E P .0→→ {.,0,1,2,3...8,9}为终结符有限集。到这一步为止，所有推出式都已经满足正则文法的要求，可见这个文法可以转化成等价的严格意义上的正则文法。 我们可以看出，这个文法构造的语言其实就是实数集，现证明了这个语言可以由一个等价的正则文法产生，因而可以判断，这是一个正则语言。 定理5.1 设L 被某个正则文法G 产生，则L 可被某个有穷自动机接

形式语言与自动机期末测试题

《形式语言与自动机》期末测试题 （规定时间：2小时） 学号姓名 1. (12 pts) 选择填空（多选）： (a) 由正规表达式a* 定义的语言；A,C（或只回答C） m m?m ?0} {a b ；B (b) 语言mm m?m ?0} c ；D{a (c) 语言b m n m?m,n ?0} c ；(d) 语言{a B b (e) 对角化（diagonalization）语言L ；F d(f) 通用语言（universal）语言L ；E u供选择的答案： A. 是某个有限状态自动机的语言； B. 是某个下推自动机的语言, 但不是任何有限状态自动机的语言； C. 是某个有限状态自动机的语言,但不是任何空栈接受方式的确定下推自动机的语言； D. 是某个可停机的图灵机的语言, 但不是任何下推自动机的语言； E. 是某个图灵机的语言, 但不是任何可停机的图灵机的语言； F. 不是任何图灵机的语言. ?, q, B, {q }）有如下转移规则：图灵机（{ q, q, q, q }, { 0,1 }, { 0,1,B }, 2. (7 pts)320013?（q, 0）=（q,1, R）10?（q, 1）=（q, 0, L）21?（q, 1）=（q, 1, R）02?（q, B）=（q, B, R）310110开始,该图灵机可以到达的完整的ID序列, 直到它停机. qID给出从初始0，，C 和 D. 3. (12 pts)设有四个语言（或问题）AB这些语言可以是，也可以不是递归可枚举语言，但已知如下条件：（此题出得不好） i. A 可以归约到B（不一定是多项式时间归约，下同）； B 可以归约到C；ii. D 可以归约到iii. C； 对于以下 6 个命题，分别指出它们是“真”，或是“假”，或是“不能确定”： (a) A 是递归可枚举的但不是递归的，而C 是递归的. 假（A 不是递归的与C是递 归的不可能同时成立） (b) B 不是递归的，而D 是递归可枚举的. 不能确定 (c) A 的补不是递归可枚举的，而B 的补是递归可枚举的. 不能确定 假. 的补是递归的C 的补不是递归的，而B (d) . 不能确定A 是递归的，那么B 的补是递归的(e) 如果 . 真是递归的，那么D 的补是递归的(f) 如果C下面的左图表示a. ?b, B?BA?a的产生式集合为：S?AS?b, A?BB?4. (11 pts) 文法G 算法时所构造的表，各集合与表元素符号之间的CYK 和字符串ababb 应用对于文法G . 试问对应关系可参照右边的图(5 pts) X 时与哪几对表元素相关？(a) 计算15{S,A,B} (5 pts) (b) X = ？15 Yes L(G)? (1 pt) (c) 是否有ababb ?XX5511XXS,A,B S }{}{5214S,B S XXA,B X}{{}}{513324?XXXS,B S S,B X}{}{}{51223344A,B S,A S,A A,B XXS,A XXX}{{}{}}{}{5541134322aaaaabbaba413255. (8 pts)对于

北邮形式语言与自动机四五章答案

形式语言与自动机作业参考答案（仅供参考） 第四章 2．最左推导：E→E+T→T+T→E+T→b+T→b+T/F→b+F/F→b+b/F→b+b/b 最右推导：E→E+T→E+T/F→E+T/b→E+F/b→E+b/b→T+b/b→F+b/b→b+b/b 8.(1)由题：S,D,E为有用非终结符，删去有关C的生成式，得：G1:S→ED,D→a,E→b (2)由题：S,D,E为有用非终结符，删去有关C的生成式，得：G2:S→D,D→bS|b,E→DS|b. 又E不可达，删去有关E得生成式，得：G2:S→D,D→bS|b 9．由题：N’={S,C,D,E},因为S∈N’，所以P1中加入生成式:S1→S|ε,变换后的无ε生成式的等价文法为：G1={N1,T,P1,S1} N1={S1,S,C,D,E} P1:S1→S|ε S→DCE,D→CC,C→EE|b,E→DD|a 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，消单生成式： N S1 = { S1,S,A1,A2,A3,A4, A5 } , N S = N A1 = N A2 = N A3 = N A4 = N A5 = { 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，变换为无ε生成式：

形式语言与自动机课后习题答案

形式语言与自动机课后作业答案第二章

4．找出右线性文法，能构成长度为1至5个字符且以字母为首的字符串。 答：G={N,T,P,S} 其中N={S,A,B,C,D} T={x,y} 其中x ∈{所有字母} y ∈{所有的字符} P 如下: S →x S →xA A →y A →yB B →y B →y C C →y C →y D D →y 6．构造上下文无关文法能够产生 L={ω/ω∈{a,b}*且ω中a 的个数是b 的两倍} 答：G={N,T,P,S} 其中N={S} T={a,b} P 如下: S →aab S →aba S →baa S →aabS S →aaSb S →aSab S →Saab S →abaS S →abSa S →aSba S →Saba S →baaS S →baSa S →bSaa S →Sbaa 7．找出由下列各组生成式产生的语言（起始符为S ） (1) S →SaS S →b (2) S →aSb S →c (3) S →a S →aE E →aS 答：（1）b(ab)n /n ≥0}或者L={(ba)n b /n ≥0} (2) L={a n cb n /n ≥0} (3) L={a 2n+1 /n ≥0} 第三章 1． 下列集合是否为正则集，若是正则集写出其正则式。 （1） 含有偶数个a 和奇数个b 的{a,b}*上的字符串集合 （2） 含有相同个数a 和b 的字符串集合 （3） 不含子串aba 的{a,b}*上的字符串集合 答：（1）是正则集，自动机如下 a a b b b b a 偶a 偶b 偶a 奇b 奇a 奇b 奇a 偶b

形式语言第四章参考答案

1.写出表示下列语言的正则表达式。 ⑴{0, 1}*。 解：所求正则表达式为：(0+1)*。 ⑵{0, 1}+。 解：所求正则表达式为：(0+1)+。 ⑶{ x│x∈{0,1}+ 且x中不含形如00的子串 }。 解：根据第三章构造的FA，可得所求正则表达式为：1*(01+)*(01+0+1)。 ⑷{ x│x∈{0,1}*且x中不含形如00的子串 }。 解：根据上题的结果，可得所求正则表达式为：ε+1*(01+)*(01+0+1)。 ⑸{ x│x∈{0,1}+ 且x中含形如10110的子串 }。 解：所求正则表达式为：(0+1)*10110(0+1)*。 ⑹ { x│x∈{0,1}+ 且x中不含形如10110的子串 }。 解：根据第三章的习题，接受x的FA为： 要求该FA对应的正则表达式，分别以q0、q1、q2、q3、q4为终结状态考虑： q0为终态时的正则表达式：(0*(11*0(10)*(ε+111*11*0(10)*)0)*)* q1为终态时的正则表达式：0*1(1*(0(10)*111*1)*(0(10)*00*1)*)*

q2为终态时的正则表达式：0*11*0((10)*(111*11*0)*(00*11*0)*)* q3为终态时的正则表达式：0*11*0(10)*1(11*11*0((10)*(00*11*0)*)*1)* q4为终态时的正则表达式：0*11*0(10)*11(1*(11*0((00*11*0)*(10)*)*11)*)* 将以上5个正则表达式用“+”号相连，就得到所要求的正则表达式。 ⑺ { x│x∈{0,1}+ 且当把x看成二进制数时，x模5与3同余和x为0时，│x│=1 且x≠0时，x的首字符为1}。 解：先画出状态转移图，设置5个状态q0、q1、q2、q3、q4，分别表示除5的余数是0、1、2、3、4的情形。另外，设置一个开始状态q.由于要求x模5和3同余，而3模5余3,故只有q3可以作为终态。由题设，x=0时，│x│=1，模5是1，不符合条件，所以不必增加关于它的状态。下面对每一个状态考虑输入0和1时的状态转移。 q: 输入1，模5是1，进入q1。 q0: 设x=5n。输入0，x=5n*2=10n，模5是0，故进入q0 输入1，x=5n*2+1=10n+1，模5是1，故进入q1 q1：设x=5n+1。输入0，x=(5n+1)*2=10n+2，模5是2，故进入q2 输入1，x=(5n+1)*2+1=10n+3，模5是3，故进入q3 q2：设x=5n+2。输入0，x=(5n+2)*2=10n+4，模5是4，故进入q4 输入1，x=(5n+2)*2+1=10n+5，模5是0，故进入q0 q3：设x=5n+3。输入0，x=(5n+3)*2=10n+6，模5是1，故进入q1 输入1，x=(5n+3)*2+1=10n+7，模5是2，故进入q2