形式语言与自动机理论第三版第三章答案

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

一、按要求完成下列填空

1. 给出集合{Φ,{Φ}}和集合{ε,0,00}的幂集 （2x4'） 2. 设∑={0,1},请给出∑上的下列语言的文法 （2x5'） (1)所有包含子串01011的串

(2)所有既没有一对连续的0，也没有一对连续的1的串 1. 构造识别下列语言的DFA (2x6) (1) {x|x?{0，1}+且x以0开头以1结尾}

(2) {x|x?{0，1}

+

且x的第十个字符为1}

二、判断（正确的写T，错误的写F） 5x2'

1.设R1和R2是集合{a,b,c,d,e}上的二元关系，则

(R1?R2)R3?R1R3?R2R3

A 2.对于任一非空集合A，Φ?2

3.文法G：S A|AS A a|b|c|d|e|f|g 是RG 4.3型语言

2型语言

1型语言

0型语言

?? 5.s（rs+s）*r=rr*s（rr*s）*

三、设文法G的产生式集如下，试给出句子aaabbbccc的至少两个不同的推导（12分）。

S?aBC|aSBC aB?ab

bB→bb

?

CB→BC bC→bc c

第三章作业答案

1．已知DFA M1与M2如图3－18所示。 (敖雪峰 02282068)

(1) 请分别给出它们在处理字符串1011001的过程中经过的状态序列。 (2) 请给出它们的形式描述。

q0S0q1q00q111010101110q2q30q2q3

图3－18 两个不同的DFA

解答：(1)M1在处理1011001的过程中经过的状态序列为q0q3q1q3q2q3q1q3;

M2在处理1011001的过程中经过的状态序列为q0q2q3q1q3q2q3q1;

(2)考虑到用形式语言表示,用自然语言似乎不是那么容易,所以用图上作业法把它们用正则表达式来描述:

M1: [01+(00+1)(11+0)][11+(10+0)(11+0)]*

10

M2: (01+1+000){(01)*+[(001+11)(01+1+000)]*}

******************************************************************************* 2．构造下列语言的DFA ( 陶文婧 0228208

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

第二章

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}

7．找出由下列各组生成式产生的语言（起始符为S） (1) S→SaS S→b (2) S→aSb S→c

其中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

(3) S→a S→aE E→aS

答：（1）b(ab)n /n≥0}或者L={(ba)nb /n≥0} (2) L={ancbn /n≥0} (3) L={a2n+1 /n≥0} 第三章 1．

下列集合是否为

关于

《结构化程序设计思想在形式语言与自动机理论中的体现》 一文中性质语言与自动机相关理论知识的分析与感悟

————戚洪源

摘 要：本文为本科阶段学习形式语言与自动机课程过程中阅读专业文献后，对于该文献中所涉及的形式语言与自动机的专业知识进行解读和分析，以及一些个人在学习形式语言与自动机课程后的感悟。

关键词：形式语言与自动机 结构化程序设计 计算机理论 正 文：

一、关于文献中形式语言与自动机相关知识的解读 （一）文章第二部分涉及到的关于正则文法的相关知识

文章的第二部分：构造文法时结构化思想的体现。在这一部分中，作者举了一个经典的正则文法的例子：

S?R?R?R0R?NBPB?N.DP?0.DN?AMA?123...89M??0M1M2M3M...8M9MD?MA

首先我们运用学过的知识将这个文法转化为一个等价的正则文法：

定义2.5 若对于文法G=(V,T,P,S),P中每个产生式都有如下形式：

A?a或A?aB,a?T????,A,B?V

则称G为正则文法。

在这个文法中，除了第三行、第四行、第五行、第八行，每一个语句都满足正则文法语句的要求。而对于第五行，可以转化为：

N?0M1M2M...8M9M

-------------精选文档-----------------

可编辑 2．1回答下面的问题： （周期律 02282067）

（1）在文法中，终极符号和非终极符号各起什么作用？

? 终结符号是一个文法所产生的语言中句子的中出现的字符，他决定了一个文法的产生语

言中字符的范围。

? 非终结符号又叫做一个语法变量，它表示一个语法范畴，文法中每一个产生式的左部至

少要还有一个非终结符号，（二，三型文法要求更严，只允许左部为一个非终结符号）他是推导或归约的核心。

（2）文法的语法范畴有什么意义？开始符号所对应的语法范畴有什么特殊意义？

? 文法的非终结符号A 所对应的语法范畴代表着一个集合L （A ），此集合由文法产生式

中关于A 的产生式推导实现的

? 开始符号所对应的语法范畴则为文法G = {V ，T ，P ，S}所产生的语言L （G ）

={w S T w w *

*|?∈且}

（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→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)nb /n≥0}

(2) L={ancbn /n≥0} (3) L={a2n+1 /n≥0}

第三章

1． 下列集合是否为

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

第二章

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)nb /n≥0}

(2) L={ancbn /n≥0} (3) L={a2n+1 /n≥0}

第三章

1． 下列集合是否为

Unit 4 [见教材P61]

Writing Between the Lines

阅读时要做读书笔记

Mortimer J. Adler（.）

莫迪摩尔. J. 阿德勒（美国）

①You know you have to read “between the lines” to get the most out of anything. ②I want to persuade you to do something equally important in the course of your reading. ③I want to persuade you to “write between the lines.” ④Unless you do, you are not likely to do the most efficient kind of reading.

①你很清楚，为了能够最充分地理解，你必须要能听读懂言外之意。

②现在，我想建议你在阅读时也要做同等重要的事，那就是建议你在阅读时做读书笔记，否则你的阅读不大可能是最有效的。

①I contend, quite bluntly, that

①坦白说，我认为，人们阅读时在书上做笔记不是毁书，而是爱书

vb程序设计教程第三版第三章

第6章 变量与过程的作用范围6.1 概 述在第2章我们介绍了VB应用程序(通常称为 工程)的组织结构，它由窗体模块、标准模块和类 模块组成。VB程序代码就保存在窗体模块文件 (*.Frm)、标准模块文件(*.Bas)或类模块文 件(*.Cls)中。它们形成了工程的一种模块层次 结构，如下图所示。

vb程序设计教程第三版第三章

一个应用程序的组成结构

vb程序设计教程第三版第三章

6.1.1 窗体模块(文件扩展名为 .FRM ) 文件扩展名为 窗体模块。窗体模块可以包含处理事件的过程、 窗体模块。窗体模块可以包含处理事件的过程、 通用过程以及变量、常数、 通用过程以及变量、常数、类型和外部过程的窗体 级声明。如果要在文本编辑器中观察窗体模块， 级声明。如果要在文本编辑器中观察窗体模块，则 还会看到窗体及其控件的描述， 还会看到窗体及其控件的描述，包括它们的属性设 置值。 置值。写入窗体模块的代码是该窗体所属的具体应 用程序专用的； 用程序专用的；它也可以引用该应用程序内的其它 窗体或对象。 窗体或对象。

vb程序设计教程第三版第三章

6.1.2 标准模块(文件扩展名为.BAS) 它们可以包含变量、常数、类型、外部 过程和全局过程

第3章 习题

3-1 试构造一右线性文法，使得它与如下的文法等价

S→AB A→UT U→aU|a D→bT|b B→cB|c

并根据所得的右线性文法，构造出相应的状态转换图。

3-2 对于如题图3-2所示的状态转换图

00D01A0B01C11F0E1题图3-2 (1) 写出相应的右线性文法； (2) 指出它接受的最短输入串； (3) 任意列出它接受的另外4个输入串； (4) 任意列出它拒绝接受的4个输入串。

3-3 对于如下的状态转换矩阵：

a b a b SA S SA BA A B A B A BB B BB B(ⅰ) 初态:S终态:B(ⅲ) 初态:S终态:Ba b a b SAA B SA