-
百度文库
-
让每个人平等地提升自我
第
1
章
引论
第
1
题
解释下列术语：
（
1
）
编
译程序
（
2
）
源
程序
（
3
）
目
标程序
（
4
）
编
译程序的前端
（
5
）
后
端
（
6
）
遍
答案：
（
1
）
编译程序：如果源语言为高级语言，目标语言为某台计算机上的汇编语言或机器语
言，则此翻译程序称为编译程序。
（
2
）
源程序：源语言编写的程序称为源程序。
（
3
）
目标程序：目标语言书写的程序称为目标程序。
（
4
）
编译程序的前端：它由这样一些阶段组成：这些阶段的工作主要依赖于源语言而与
目标机无关。通常前端包括词法分析、语法分析、语义分析和中间代码生成这些阶
< br>段，某些优化工作也可在前端做，也包括与前端每个阶段相关的出错处理工作和符
号表管理等工作。
（
5
）
后端：指那些依赖于目标机而一般不依赖源语言，只与中间代码有关的那些阶段，
即目标代码生成，以及相关出错处理和符号表操作。
（
6
）
遍：是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。
第
2
题
一个典型的编译程序通常由哪些部分组成？各部分的主要功能
是什么？并画出编译程序
的总体结构图。
答案：
一
个典型的编译程序通常包含
8
个组成部分，它们是词法分析程序
、语法分析程序、语
义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成
程序、表格管理程序和
错误处理程序。其各部分的主要功能简述如下。
< br>
词法分析程序：输人源程序，拼单词、检查单词和分
析单词，输出单词的机内表达形式。
语法分析程序：检查源程序中存在的形式语法错误，输出错误处理信息。
语义分析程序：进行语义检查和分析语义信息，并把分析的结
果保存到各类语义信息表
中。
中间代码生成程序：按照语义规则，将语法分析程序分析出的语法单位转换成一定形式
的中间语言代码，如三元式或四元式。
<
/p>
中间代码优化程序：为了产生高质量的目标代码，对中间代码进行等价变换处理。目标代码
生成程序：将优化后的中间代码程序转换成目标代码程序。
3
百度文库
-
让每个人平等地提升自我
表格管理程
序：负责建立、填写和查找等一系列表格工作。表格的作用是记录源程序的
各类信息和编
译各阶段的进展情况，编译的每个阶段所需信息多数都从表格中读取，产生的
中间结果都
记录在相应的表格中。可以说整个编译过程就是造表、查表的工作过程。需要指
出的是，
这里的“表格管理程序”并不意味着它就是一个独立的表格管理模块，而是指编译
程序具
有的表格管理功能。
错误处理程序
：处理和校正源程序中存在的词法、语法和语义错误。当编译程序发现源
程序中的错误时
，错误处理程序负责报告出错的位置和错误性质等信息，同时对发现的错误
进行适当的校正（修复）
，目的是使编译程序能够继续向下进行分析和处理
。
注意：
如果问编译程序有哪些主要构成成分，只要回答六部分就可以。如果搞不清楚，
就回答八
部分。
第
3
题
何谓翻译程序、编译程序和解释程序？它们三者之间有何种关
系？
答案：
翻
译程序是指将用某种语言编写的程序转换成另一种语言形式的程序的程序，如编译程
序和
汇编程序等。
编译程序是把用高级
语言编写的源程序转换（加工）成与之等价的另一种用低级语言编
写的目标程序的翻译程
序。
解释程序是解释、执行高级语
言源程序的程序。解释方式一般分为两种：一种方式是，
源程序功能的实现完全由解释程
序承担和完成，即每读出源程序的一条语句的第一个单词，
则依据这个单词把控制转移到
实现这条语句功能的程序部分，该部分负责完成这条语句的功
能的实现，完成后返回到解
释程序的总控部分再读人下一条语句继续进行解释、执行，如此
反复；另一种方式是，一
边翻译一边执行，即每读出源程序的一条语句，解释程序就将其翻
译成一段机器指令并执
行之，然后再读人下一条语句继续进行解释、执行，如此反复。无论
是哪种方式，其加工
结果都是源程序的执行结果。目前很多解释程序采取上述两种方式的综
3
百度文库
-
让每个人平等地提升自我
合实现方案
，即先把源程序翻译成较容易解释执行的某种中间代码程序，然后集中解释执行
中间代码
程序，最后得到运行结果。
广义上
讲，编译程序和解释程序都属于翻译程序，但它们的翻译方式不同，解释程序是
边翻译（
解释）边执行，不产生目标代码，输出源程序的运行结果。而编译程序只负责把源
程序翻
译成目标程序，输出与源程序等价的目标程序，而目标程序的执行任务由操作系统来
完成
，即只翻译不执行。
第
4
题
对下列错误信息，请指出可能是编
译的哪个阶段（词法分析、语法分析、语义分析、代
码生成）报告的。
< br>
（
1
）
else
没有匹配的
if
（
2
）
数组下标越界
（
3
）
使用的函数没有定义
（
4
）
在数中出现非数字字符
答案：
（
1
）
语法分析
（
2
）
语义分析
（
3
）
语法分析
（
4
）
词法分析
第
5
题
编译程序大致有哪几种开发技术？
答案：
（
1
）自编译：用某一高级语言书写其本身的编译程序。
（
2
< br>）交叉编译：
A
机器上的编译程序能产生
B
机器上的目标代码。
（
3
）自展：首先确定一个非常简单的核心语言
L0
，用机器语言或汇编语言书写出它的
编
译程序
T0
，再把语言
L0
扩充到
L1
，此时
L0
?
L1
,
并用
L0
编写
L1
的编译程序
T1
，再把语
言
L1
扩充为
L2
，有
L1
?
L2
,
并用
L1
编写
L2
的编译程序
T2
，……，如此逐步扩展下
去，
好似滚雪球一样，直到我们所要求的编译程序。
（
4
）移植
：将
A
机器上的某高级语言的编译程序搬到
B
机器上运行。
3
百度文库
-
让每个人平等地提升自我
第６题
计算机执行用高级语言编写的程序
有哪些途径
?
它们之间的主要区别是什么
?
答案：计算机执行用高级语言编写的程序主要途径有两种，即解释与编译。
像
Basic
之类的语言，属于解释型的高级语言。它们的特点是计算机并不事先对高级语
言进行全盘翻译，将其变为机器代码，而是每读入一条高级语句，就用解释器将其翻译为一
< br>
条机器代码，予以执行，然后再读入下一条高级语句，翻译为机器代码，再执行
，如此反
复。
总而言之，是边翻译边执行。
像
C
，
Pasca
l
之类的语言，属于编译型的高级语言。它们的特点是计算机事先对高级语
言进行全盘翻译，将其全部变为机器代码，再统一执行，即先翻译，后执行。从速度上看，
编译型的高级语言比解释型的高级语言更快。
3
百度文库
-
让每个人平等地提升自我
第
2
章
PL/0
编译程序的实现
第
1
题
PL/0
语言允许过程嵌套定义和递归调用，试问它的编译程序如何解决运行时的存储管
理。
答案：
PL/0
语言允许过程嵌套定义和递归调用，它的编译程序在
运行时采用了栈式动态存储
管理。
（数组
CODE
存放的只读目标程序，它在运行时不改变。
）运行时的数据区
S
< br>是由解
释程序定义的一维整型数组，解释执行时对数据空间
S
的管理遵循后进先出规则，当每个
过程
(
包括主程序
)
被调用时，才分配数据空间，退出过程时，则所分配的数据空间被释放。
<
/p>
应用动态链和静态链的方式分别解决递归调用和非局部变量的引用问题。
< br>
第
2
题
若
PL/0
编译程序运行时的存储分配策略采用栈式动态分配，
并用动态链和静态链的方
式分别解决递归调用和非局部变量的引用问题，试写出下列程序
执行到赋值语句
b
∶
=10
时运行栈的布局示意图。
var x,y;
procedure p;
var a;
procedure q;
var b;
begin
(q)
b
∶
=10;
end (q);
procedure s;
var c,d;
procedure r;
var e,f;
begin (r)
call q;
end
(r);
begin (s)
call r;
end (s);
begin (p)
call s;
end (p);
begin
(main)
call p;
end
(main).
答案：
程序执行到赋值语句
b
∶
=10
时运行栈的布局示意图为：
3
百度文库
-
让每个人平等地提升自我
第
3
题
写出题
2
中当程序编译到
r
的过程体时的名字表
table
的内
容。
name
答案：
题
2
中当程序编译到
r
的过程体时的名字表
table
的内容为：
name
x
y
p
a
q
s
c
d
kind
variable
variable
procedure
variable
procedure
procedure
variable
variable
level/val
0
0
0
1
1
1
2
2
adr
dx
dx+1
过程
p
的入口（待填）
dx
过程
q
的入口
过程
s
的入口（待填）
dx
dx
size
5
4
5
kind
level/val
adr
size
3
百度文库
-
让每个人平等地提升自我
r
e
f
procedure
variable
variable
2
3
3
过程
r
的入口
dx
dx+1
5
注意：
q
和
s
是并列的过程，所以
q
定义的变量
b
被覆盖。
第
4
题
指出栈顶指针
T
，最新活动记录基地址指针
B
，动态链指针
DL
，静态链指针
SL
与
返回地址
RA
的用途。
答案：
栈顶指针
T
，最新活动记录基地址指针
B
，动态链指针
DL
，静态链指针
SL
与返回地址
RA
的用途说明如下：
T
：
栈顶寄存器
T
指出了当前栈中最新分配的单元
(T
也是数组
S
的下标
)
。
B
：基
址寄存器，指向每个过程被调用时，在数据区
S
中给它分配的数据段起
始
地址，
也称基地址。
SL
：
静态
链，指向定义该过程的直接外过程（或主程序）运行时最新数据段的基地址，
用以引用非
局部（包围它的过程）变量时，寻找该变量的地址。
DL
：
动态链，指向调用该过程前正在运行过程的数据段基地址，用以过程执行结束释放
数据空间时，恢复调用该过程前运行栈的状态。
RA
：
返回
地址，记录调用该过程时目标程序的断点，即调用过程指令的下一条指令的地
址，用以过
程执行结束后返回调用过程时的下一条指令继续执行。
在每个过程被调用时在栈顶分配
3
个联系单元，用以存放
SL
，
DL
，
RA
。
第
5
题
PL/0
编译程序所产生的目标代码是一种假想栈式计算机的汇编语言，请说明该汇编语
言中下
列指令各自的功能和所完成的操作。
（１）
INT 0 A
（２）
OPR 0 0
（３）
CAL L A
答案：
PL/0
编译程序所产生的目标代码中有
3
条非常重要的特殊指令，这
3
条指令在
code
中的位置和功能以及所完成的操作说明如下：
INT 0 A
在过程目标程序的入口处，开辟
A
个单元的数据段。
A
为局部变量的个
数
+3
。
OPR 0 0
3
百度文库
-
让每个人平等地提升自我
<
/p>
在过程目标程序的出口处，释放数据段（退栈）
，恢复调用该过程
前正在运行的过程的数
据段基址寄存器
B
和栈顶寄存器
T
的值，并将返回地址送到指令地址寄存器
P
中，以使调
用前的程序从断点开始
继续执行。
CAL L A
调用过程，完成填写静态链、动态链、返回地址，给出被调用过程的基地址值，送入基址
寄存器
B
中，目标程序的入口地址
A
的值送指令地址寄存器
P
中，使指令从
A
开始执
行。
第
6
题
给出对
PL/0
语言作如下功能扩充时的语法图和
EBNF
的语法描述。
(1)
扩充条件语句的功能使其为：
if
〈条件〉
then
〈语句〉
[else
〈语
句〉
]
(2)
扩充
repeat
语句为：
repeat
〈语句〉
{
；
〈语句〉
}unti
l
〈条件〉
答案：
对
PL/0
语言作如下功能扩充时的语法图和
EBNF
的语法描述如下：
(1)
扩充条件语句的语法图为：
EBNF
的语法描述为：
〈条件语句〉
::= if
〈条件〉<
/p>
then
〈语句〉
[else
〈语句〉
]
(2)
扩充
repeat
语句的语法图为：
EBNF
的语法描述为：
〈
重复语句〉
::= repeat
〈语
句〉
{
；
〈语句〉
}until
〈条件〉
3
百度文库
-
让每个人平等地提升自我
第
3
章
文法和语言
第
1
题
文法
G<
/p>
＝
({A,B,S},{a,b,c},P,S)
其中
P
为：
S→Ac|aB
A→ab
B→bc
写出
L(G[S])
的全
部元素。
答案：
L(G[S])={abc}
第
2
题
文法
G[N]
为：
N
→
D|ND
D
→
0|1
|2|3|4|5|6|7|8|9
G[N]
的语言是什么？
答案
:
G[N]
的语言是
V+
。
V={0,1,2,3,4,5,6,7,8,9}
N=>ND=>NDD....
=>NDDDD...D=>D......D
或者：允许
0
开头的非负整数？
第３题
为只包含数字、加号和减号的表达式，例如
< br>9-2
＋
5
，
< br>3-1
，７等构造一个文法。
答案：
G[S]:
S->S+D|S-D|D
D->0|1|2|3|4|5|6|7|8|9
第
4
题
已知文法
G[Z]
：
Z
→
aZb|ab
写出
L(G[Z])
的全部元素。
3
百度文库
-
让每个人平等地提升自我
答案：
Z=>aZb=>aaZbb=>aaa..Z...bbb=>
aaa..ab...bbb
第
5
题
写一文法，使其语言是偶正整数的集合。
要求：
(1)
允许
0
打头；
(2)
不允许
0
打头。
答案：
(1)
允许
0
开头的偶正整数集
合的文法
E→NT|D
T→NT|D
N→D|1|3|5|7|9
D→0|2|4|6|8
(2)
不允许
0
开头的偶正整数集合的文法
E→NT|D
T→FT|G
N→D|1|3|5|7|9
D→2|4|6|8
F→N|0
G→D|0
第
6
题
已知文法
G
：
<
表达式
>::=<
项
>
｜
<
表
达式
>
＋
<
项
>
<
项<
/p>
>::=<
因子
>
｜
<
项
>*<
因子
>
<
因子
>::=
（
<
< br>表达式
>
）｜
i
试给出下述表达式的推导及语法树。
（５）
i
+(i+i)
（６）
i
+i*i
n n
L(G[Z])={a b
|n>=1}
3
百度文库
-
让每个人平等地提升自我
答案：
(5)
<
表达式
>
=><
表达式
>
＋
< br><
项
>
=><
表达式
>
＋
<
因子
>
=><
表达式
>
＋（
<
表达式
>
）
=><
表达式
>
＋（
<
表达式<
/p>
>
＋
<
项
>
）
=><
表达式
>
＋（
<
表达式
>
＋
<
因子
>
）
=><
表达式<
/p>
>
＋（
<
表达式
>
＋
i
）
=><
表达式
>
＋（
<
项
>
＋
i
）
=><
表达式
>
＋
（
<
因子
>
＋
i
）
=><
表达式
>
＋
（
i
＋
i
）<
/p>
=><
项<
/p>
>
＋（
i
＋
i
）
=><
因子
>
＋（
i
＋
i
）
=>i
＋（
i
＋
i
）
3
<
表
达式
>
<
表
达式
>
+
<
项
>
<
项
>
<
因
子
>
<
因
子
>
（
<
表
达式
>
)
i
<
表
达式
>
+
<
项
>
<
项
>
<
因
子
>
<
因
子
>
i
i
百度文库
-
让每个人平等地提升自我
<
表
达式
>
(6)
<
表达式
>
=><
表达式
>
＋
< br><
项
>
=><
表达式
>
＋
<
项
>*<
因子
>
<
表
达式
>
<
/p>
=><
表达式
>
＋
<
项
>*i
=><
表
达式
>
＋
<
因
子
>*i
=><
< br>表达式
>
＋
i*i
<
项
>
=><
项
>
＋
i*i
=><
因子
>
＋
i*i
<
因
子
>
=>i
＋
i
*i
i
第
7
题
证明下述文法
G[
< br>〈表达式〉
]
是二
义的。
〈表达式〉∷
=a|(
〈表达式〉
)|
〈表达式〉<
/p>
〈运算符〉
〈表达式〉
〈运算符〉∷
=+|-|*|/
答案：可为句子
a+a*a
构造两个不同的最右推导
:
最右推
导
1
〈表达式〉
〈表
达式〉
〈运算符〉
〈表达式〉
〈表达式〉
〈运算符〉
a
〈表达式〉
* a
〈表达式〉
〈运
算符〉
〈表达式〉
* a
〈表达式〉
〈运算符〉
a * a
〈表达式〉
+
a * a
a + a * a
最右推导
2
〈表达式〉
〈表达式〉
〈运算符〉
〈表达式〉
符〉
〈表达式〉
〈运算符〉
〈表达式〉
〈表达式〉
〈运算符〉
〈表达式〉
〈运算符〉
a
〈表达式〉
〈运
算符〉
〈表达式〉
* a
〈表达式〉
〈运算符〉
a * a
〈表达式〉
+
a * a
a + a * a
第
8
题
文法
G[S]
为：
S
→
Ac|aB
3
+
<
项
>
<
项
>
*
<
因
子
>
<
因
子
>
i
i
〈表达式〉
〈运算
百度文库
-
让每个人平等地提升自我
A
→
ab
B
→
bc
该文法是否为二义的？为什么？
答案：
对于串
abc
(1)S=>Ac=>abc (2)S=>aB=>abc
即存在两不同的最右推导。所以，该文法是二义的。
或者：
对输入字符串
abc
，能构造两棵不同的语法树，所以它是二义
的。
第
9
题
答案：
第
10
题
S
S
a
B
A
c
a
b
c
b
考虑下面上下文无关文法：
S
→
SS*|SS+|a
(1)
表明通过此文法如何生成串
<
/p>
aa+a*
，并为该串构造
语法树。
(2)G[S]
的语言是什么？
S
S
S
S
*
S
+
a
(1)
此文法生成串
aa+a*
的最右推导如下
S=>SS*=>SS*=>Sa*=>SS+a*=>Sa+a*=>aa+a*
(2)
该文法生成的语言是：
*
和
+
的后缀表达式
，即逆波兰式。
a
a
3
百度文库
-
让每个人平等地提升自我
文法
S
→
S(S)S|ε
(1)
生成的语言是什么？
(2)
该文法是二义的吗？说明理由。
答案：
（１）
嵌套的括号
（２）
是二义的，因为对于（）
（）可以构造两棵不同的语法树。
第
11
题
令文法
G[E]
为：
E→T|E+T|E-T
T→F|T*F|T/F
F→(E)|i
证明
E+T*F
是它的一个句型，指出这个句型的所有短语、直接短语和句柄。
答案：
此句型对应语法树如右，故为此文法一个句型。
或者：因为存在推导序列
:
E=>E+T=>E+T*F
，所
以
E+T*F
句型
此句型相对于
E
< br>的短语有
:E+T*F
；相对于
T
的短
语
有
T*F
直接短语为：
T*F
句柄为：
T*F
第
13
题
一个上下文无关文法生成句子
abbaa
的推导树如下：
(1)
给出串
abbaa
最左推导、最右推导。
(2)
该文法的产生式集合
P
可能有哪些元
素？
(3)
找出该句子的所有短语、直接
短语、句
a
答案：
(1)
串
abbaa
最左推导
:
a
S
ε
B
b
B
A
b
a
A
B
S
S
柄。
3
百度文库
-
让每个人平等地提升自我
S=>
ABS=>aBS=>aSBBS=>aBBS=>abBS=>abbS=>abbAa=>abbaa
最右推导：
S=>ABS=>ABAa=>ABaa=>ASBBaa=
>ASBbaa=>ASbbaa=>Abbaa=>abbaa
(2)
产
生式有：
S
→
ABS |Aa|ε
A
→
a
B
→
SBB|b
可能元素有：
ε aa
ab
abbaa aaabbaa ……
(3)
该句子的短语有：
a
是相
对
A
的短语
ε
是相对
S
的短语
b
是相对
B
的短语
εbb
是相对
B
的短语
aa
是相对
S
的
短语
aεbbaa
是相对
S
的短语
直接短语有：
a ε b
句柄是：
a
第
14
题
给出生成下述语言的上下文无关文法：
（
1
）
{ a
n
b
n
a
m
b
m
|
n
，
m>=0}
（
2
）
{
1
n
0
m
1
m
0
n
|
n
，
m>=0}
< br>（
3
）
{WaWr|W
属于
{0|a}*
，
Wr
表示
W
的逆
}
答案：
（１）
S→AA
A→aAb|ε
（２）
S→1S0|A
A→0A1|ε
（３）
S
→
0S0|1S1|
ε
3
百度文库
-
让每个人平等地提升自我
第
16
题
给出生成下述语言的三型文
法：
(1){an|n >=0 }
(2) { a
n
b
< br>m
|n,m>=1 }
(
3){a
n
b
m
c
k
|n,m,k>=0 }
答案：
(1)
S→aS|
ε
(2)
S→aA
A→aA|B
B→bB|b
(3)
A→aA|B
B→bB|C
C→cC|ε
第
17
题
习题７和习题
11
中的文法等价吗？
答案：
等价。
第
18
题
解释下列术语和概念：
（１）
字母表
（２）
（３）
（１）字母表：是一个非空有穷集合。
串、字和句子
语言、语法和语义
答案：
（２）串：符号的有穷序列。字：字母表中的元素。句子：如果
Z x , x
+
∈
V *T
则称
x
是文法
G
的一个句子。
（３）语言：它是由句子组成的集合，
是由一组记号所构成的集合。程序设
计的语言就是所
有该
语言的程序
的全体。语言可以看成在一个基本符号集上定义的，按一定规则构成的一切基
本符号串组成的集合。
3
百度文库
-
让每个人平等地提升自我
语法：
表示构成语言句子的各个记号之间的组合规律。程序的结构或形式。
语义：表示按照各种表示方法所表示的各个记号的特定含义。
语言所代表的含义。
3
百度文库
-
让每个人平等地提升自我
附加题
问题
1
：
给出下述文法所对应的正规式：
S→0A|1B
A→1S|1
B→0S|0
答案：
R =
(01 | 10) ( 01 | 10 )
*
问题
2
：
已知文法
G[A]
，写出它定义的语言描述
G[A]: A →
0B|1C
B
→ 1|1A|0BB
C
→ 0|0A|1CC
答案
:
G[A]
定义的语言由
0
、
1
符号串组成，串中
0
和
1
的个数相同
.
问题
3
：
给出语言描述，构造文法
.
构造一文法
,
其定义的语言是由算符
+, *,
(,)
和运算对象
a
构成的算术表达式的集合
.
答案一：
G[E] E→E+T|T
T→T
*
F|F
F→(E)|a
答案二：
G[E] E→E+E|E
*
E|(E)|a
问题
4
：
已知文法
G[S]:
S
→
dAB
A
→
aA|a
B
→ε
|bB
3
百度文库
-
让每个人平等地提升自我
相应的正规
式是什么？
G[S]
能否改写成为等价的正规文法？
答案：
正规式是
daa*b*
；
相应的正规文法为
(
由自动机化简来
)
：
G[S]:S
→
dA
A
→
a|aB
B
→
aB|a|b|bC
C
→
bC|b
也可为
(
观察得来
):G[S]:S
→
dA
A
→
a|aA|aB
B
→
bB|
ε
问题
5
：
已知文法
G
：
E→E+T|E-T|T
T→T*F|T/F|F
F→(E)|i
试给出下述表达式的推导及语法树
(1)
i;
(2)
i*i+i
(3)
i+i*i
(4)
i+(i+i)
答案：
(1)E=>T=>F=>i
(2)E=>E+T=>T+T=>T*F+T=>F*F+
T=>i*F+T=>i*i+T=>i*i+F=>i*i+i
< br>(3)E=>E+T=>T+T=>F+T=>i+T=>i+T*F=>i+F*F=>i+i*F=> i+i*i
(4)E=>E+T=>T+T=>F+T=>
i+T=>i+F=>i+(E)=>i+(E+T)=>i+(T+T)=>i+(F+T)
=>i+(i+T)=>i+(i+F)=>i+(i+i)
E
E
+ T
T
T
*
F
F i
E
i
E + T
T
F
F
i
i
i
E + T
T
F
(
E )
F
i
E
+
T
T
F
F
i
(4)
E
T
F
F
i
3
百度文库
-
让每个人平等地提升自我
i
(1)
问题
6
：
已知文法
G[E]:
E
→
ET+|T
T
→
TF*
| F
F
→
F^ | a
< br>试证：
FF^^*
是文法的句型，指出该句型的短语、简
单短语和句柄
.
答案：
该句型对应的语法树如下：
该句型相对于
E
的短语有
FF^^*
相对于
T
的短语有
FF^^*,F
相对于
F
的短语有
F^;F^^
简单短
语有
F;F^
句柄为
F.
问题
7
：
适当变换文法，找到下列文法所定义语言的一个无二义的文法：
S
→
SaS
?
SbS
?
ScS
?
d
答案：
该文法的形式很典型，可以
先采用优先级联规则变换文法，然后再规定结合性对文法做进
一步变换，即可消除二义性
。
设
a
、
b
和
c
的优先级别依次增高，根据优先级联规则将文法变换为：
S
→
SaS
?
A
A
→
AbA
?
C
i
(2)
(3)
3
百度文库
-
让每个人平等地提升自我
C
→
CcC
?
d
规定结合性为左结合，进一步将文法变换为：
S
→
SaA
?
A
A
→
AbC
?
C
C
→
CcF
?
F
F
→
d
该文法为非二义的。
问题
8
：构
造产生如下语言的上下文无关文
法：
（
1
）
{a
n
b
2n
c
m
|
n
，
m ≥ 0}
（
2
）
{a
n
b
m
c
2m
|
n
，
m ≥ 0}
（
3
）
{
a
m
b<
/p>
n
?
m
≥
n
}
（
4
）
{
a
m
b
n
c
p
d
q
?
m+n
=
p+q
}
（
5
）
{
uawb
?
u,w
∈
{
a
,
b
}*
∧
|
u
| = |
w
| }
答案：
（
1
）
根据上下文无关文法的特点，要产生形如
a
n
b
2n
c
m
的串，可以分别产生形如
a
n
b
2n
和
形如
c
m
的串。设计好的文法是否就是该
语言的文法？严格地说，应该给出证明。但若不是
特别指明，通常可以忽略这一点。
对于该语言，存在一个由以下产生式定义的上下文无关文法
G[S]
：
S
→
AB
A
→
ε
?
aAbb B
→
ε
?
cB
（
2
）
同样，要产生形如
a
n
b
m
c
2m
的串，可以分别产生形如
a
n
和形如
b
m
c
2m
的串。对于该
语言，存在一个由以下产生式定义的上下文无关文
法
G[S]
：
S
→
AB
A
→
ε
?
aA
B
→
ε
?
bBcc
（
3
）
考虑在先产生同样数目的
a,b
，然后再生成多余的
a
。以下
G[S]
是一种解法：
S
→
aSb
?
aS
?
ε
3
百度文库
-
让每个人平等地提升自我
（
4
）
以下
G[S]
是一种解法：
S
→
aSd
?
A
?
D
A
→
bAd
?
B
D
→
aDc
?
B
B
→
bBc
?
ε
注：
a
不多于
d
时，
b
不少于
c
；反之，
a
不少于
d
时，
b
不多于
c
。
前一种情形通过对
应
A
，后一种情形对应
D
。
（
5
）
以下
G[S]
是一种解法：
S
→
Ab
A
→
BAB
?
a B
→
a
?
b
问题
9
：
下面的文法
G(S)
描述由命题变量
p
、
q
，联结词
∧
（合取）
、
∨
（析取）
、
?
（否定）构
成的命题公式
集合：
S
→
S
∨
T
?
T
T
→
T
∧
F
?
F
F
→
?
F
?
p
?
q
试指出句型
?
F
∨
?
q
∧
p
的直接短语（全部）以及句柄。
答案：
直接短语：
p
，
q
，
?
F
句柄：
?
F
问题
10
：
设字母表
A={a}
，符号串
x=aaa
，写出下列符号串及其长度：
x0,xx,
x5
以及
A+.
答案：
x
0
=(a
aa)
0
=
ε
|
x
0
|=0
xx=aaaaaa
|xx|=6
x
5
=aaaaaaaaaaaaaa
a | x
5
|=15
A
+
=A
1
∪
A
2
∪ ∪
…. A
n
∪
…={a,aa,aaa,aaaa,aaaaa…}
A* = A
0
∪
A
1
∪
A
2
∪
….
∪
A
n
∪
…
={
ε
,a,aa,aaa,aaaa,aaaaa…}
问题
11
：
令∑
={
a
，
b
，
c}
，又令
x=abc
< br>，
y=b
，
z=aab
，写出如下符号串及它们的长度：
xy
，
xyz
，
（
xy
）
3
3
百度文库
-
让每个人平等地提升自我
答案：
xy=abcb |xy|=4
xyz=abcbaab
|xyz|=7
(xy)
3
=(abcb)
3
=abcbabcbabcb | (xy)
3
|=12
问题
12
：
已知文法
G[Z]
< br>：
Z
∷
=U0
< br>∣
V1
、
U
∷
=Z1
∣
1
、
V
∷
=
Z0
∣
0 ,
请写出全部由此文法描述
的只含有四个符号的句子。
答案：
Z=>U0=>Z10=>U010=>1010
Z=>U0=>Z10=>V110=>0110
Z=>V1=>Z00=>U000=>1000
Z=>V1=>Z00=>V100=>0100
问题
13
：
已知文法
G[S]
：
S
∷
=AB A
∷
< br>=aA
︱ε
B
∷
=bBc
︱
bc ,
写出该文法描述的语言。
答案：
A
∷
=aA
︱ε
描述
的语言
: {a
n
|n>=0}
B
∷
=bB
c
︱
bc
描述的语言
< br>:{,b
n
c
n
|n>=1}
L(G[S])={a
n
b
m
c
< br>m
|n>=0,m>=1}
问题
14
：
已知文法
E
∷
=T
∣
E
+T
∣
E-T
、
T
∷
=F
∣
T*F
∣
T
/F
、
F
∷
=(E)
∣
i
，写出该文法的开始<
/p>
符号、终结符号集合
V
T
、非终结符号集合
V
N
。
答案：
开始符号：
E
V
T
={+, - , * , /
,
（
,
）
, i}
V
N
={E , F , T}
3
百度文库
-
让每个人平等地提升自我
问题
15
：
设有文法
G[S]
：
S
∷
=S*S|S+S|(S)|a
，该文法是二义性文法吗？<
/p>
答案：
根据所给文法推导出句子
a+a*a
，画出了两棵不同的语法树，所以该文法是二义性文
法。
S
S
*
S
S
+
S
a
a
a
问题
16
：
写一文法，使其语言是奇正整数集合。
答案：
A::=1|3|5|7|9|NA
N::=N0|N1|N2|N3|N4|N5|N6|N7|N8|N9|
N::=0|1|2|3|4|5|6|7|8|9
3
S
S
+
S
a
S
*
S
a
a
百度文库
-
让每个人平等地提升自我
第
4
章
词法分析
第
1
题
构造下列正规式相应的
DFA.
（１）
1(0|1)
*101
（２）
１
(1010*|1(010)*1
）
*
0
（３）
a((a|b)*|ab*a)*b
（４）
b((ab)*|bb)*ab
答案：
(1)
先构造
NFA
：
用子集法将
NFA
确定化
.
X
A
AB
AC
ABY
0
.
A
AC
A
AC
1
A
AB
AB
ABY
AB
除
X
，
A
外，重新命名其他状态，令
AB
为
B
、
AC
为
C
、
ABY
为
D
，因为
D
含有
Y
（
NFA
的终态）
，所以
D
为终态。
.
X
A
B
C
D
DFA
的状态图：
:
0
.
A
C
A
C
1
A
B
B
D
B
3
百度文库
-
让每个人平等地提升自我
先
构造
NF
A
：
(2)
0
ε
1
A
ε
ε
F
B
1
C
0
ε
1
G
0
H
1
I
0
ε
J
1
K
D
1
E
ε
L
ε
ε
0
Y
X
用子集法将
NFA
确定化
X
T
0
=X
A
T
1
= ABFL
Y
CG
T
2
= Y
T
3
=
CGJ
DH
K
T
4
= DH
EI
T
5
= ABFKL
T
6
=
ABEFIL
EJY
T
7
=
ABEFGJL
Y
EHY
CGK
T
8
=
ABEFHL
Y
EY
CGI
T
9
= ABCFGJKL
DHY
T
10
=
ABEFL
Y
ε
X
ABFL
Y
CGJ
DH
ABFKL
ABEFIL
ABEFGJL
Y
ABEFHL
Y
ABCFGJKL
ABEFL
Y
CGJI
DHY
0
Y
DH
Y
EJY
EHY
EY
DHY
EY
1
A
CG
K
EI
CG
CG
CGK
CGI
CGK
CG
3
百度文库
-
让每个人平等地提升自我
T
11
= CGJI
DHJ
T
12
= DHY
T
13
=
DHJ
EIK
T
14
= ABEFIKL
DHJ
ABEFIKL
DHJ
EJY
K
EI
EIK
CG
将
T
0
、
T
1
、
T
2
、
T
3
、
T
4
< br>、
T
5
、
T
6
、
T
7
、
T
8
、
T
9
、
T
10
、
T
11
、
T
12
、
T
13
、
T
14
重新命名，分别用
0
、
1
、
2
、
3
、
4
、
5
、
6
、
7
< br>、
8
、
9
、
10
、
11
、
12
、
13
、
14
表示。因为
2
、
7
、
< br>8
、
10
、
12
中含
有
Y
< br>，所以它们都为终态。
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
0
2
4
2
7
8
10
12
10
13
7
1
1
3
5
6
3
3
9
11
9
3
5
6
14
3
3
百度文库
-
让每个人平等地提升自我
(3)
先构造
NFA
：
先构造
NFA
：
ε
ε
X
a
A
ε
D
1
a,b
B
b
a
E
a
ε
ε
F
ε
C
b
Y
0
1
1
0
X
2
0
5
1
6
0
7
1
1
9
1
0
1
1
1
1
3
1
0
4
1
1
2
0
1
0
0
0
8
0
1
1
1
0
1
3
1
1
4
用子集法将
NFA
确定化
ε
X
a
b
3
百度文库
-
让每个人平等地提升自我
T
0
=X
A
T
1
=ABCD
BE
BY
T
2
=ABCDE
BEF
BEY
T
3
=ABCDY
T
4
=ABCDEF
T
5
=ABCDEY
ABCD
ABCDE
ABCDY
ABCDEF
ABCDEY
A
BE
BEF
BE
BEF
BEF
BY
BEY
BY
BEY
BEY
将
T
0
、
T
1
、
T
2
、
T
3
、
T
4
< br>、
T
5
重新命名，分别用
0
、
1
、
2
、
3
、
4
、
5
表示。因为
3
、
5
中含
有
Y
，所以它们都为终态。
0
1
2
3
4
5
0
a
1
a
2
b
3
a
1
2
4
2
4
4
b
3
5
3
5
5
(4)
先构造
NFA
：
b
b
5
b
a
a
4
a
a
b
3
百度文库
-
让每个人平等地提升自我
ε
ε
ε
X
b
A
ε
F
B
a
C
b
ε
b
G
b
H
ε
ε
D
ε
E
a
I
b
Y
用子集法将
NFA
确定化：
X
T
0
=X
A
T
1
=ABDEF
CI
G
T
2
=CI
DY
T
3
=G
H
T
4
=ABDEFY
T
5
=ABEFH
将
T
0
、
T
1
、
T
2
、
T
3
、
T
4
< br>、
T
5
重新命名，分别用
0
、
1
、
2
、
3
、
4
、
5
表示。因为
4
中含有
Y
，
所以它为终态。
0
1
2
3
4
a
2
2
b
1
3
4
5
3
ε
X
ABDEF
CI
G
ABDEFY
ABEFH
a
CI
CI
CI
b
A
G
DY
H
G
G
3
百度文库
-
让每个人平等地提升自我
5
DFA
的状态图：
3
2
3
0
b
1
b
3
a
b
b
2
b
5
b
a
a
4
百度文库
-
让每个人平等地提升自我
第２题
已知
<
/p>
NFA
＝（
｛
x
,y,z
｝
,{0,1},M,{x},{z}
）
，其中：
M(x,0)={z}
，
M(y,0)={x,y}
，
,
M(z,0)={x,z}
，
M(x
,1)={x}
，
M(y,1)=
φ，
M(z,1)={y}
，构造相应的
DFA
。
答案：
先构造其矩阵
x
y
z
用子集法将
NFA
确定化：
x
z
xz
y
xy
xyz
将
x
、
z
、
xz
、
y
、
xy
、
xyz
重新命名，分别用
< br>A
、
B
、
C
、
D
、
E
、
F
表示。因为
B
、
C
、
F
中含有
z
，所以它为终态。
A
B
C
D
E
F
0
B
C
C
E
F
F
1
A
D
E
A
E
0
z
xz
xz
xy
xyz
xyz
1
x
y
xy
x
xy
0
z
x,y
x,z
1
x
y
3
百度文库
-
让每个人平等地提升自我
DFA
的状态图：
1
1
0
1
D
A
B
0
0
E
1
C
0
0
0
F
1
第
3
题
将下图确定化：
答案：
用子集法将
NFA
确定化：
.
S
VQ
QU
VZ
V
QUZ
Z
0
VQ
VZ
V
Z
Z
VZ
Z
1
QU
QU
QUZ
Z
.
QUZ
Z
重新命名状态子集，令
VQ
为
A
、
QU
为
B
、
VZ
为
C
、
V
为
D
、
QUZ
为
E
、
Z
为
F
。
.
0
1
3
百度文库
-
让每个人平等地提升自我
S
A
B
C
D
E
F
DFA
的状态图：
A
C
D
F
F
C
F
B
B
E
F
.
E
F
第
4
题
将下图的（
a
）和（
b
）分别确定化和最小化：
答案：
初始分划得
Π0
：终态组
{0}
，非终态组
{1,2,3,4,5}
对非终态组进行审
查：
3
百度文库
-
让每个人平等地提升自我
{1,2,3,4,5}a
{1,2,3,4,5}
∵
{4} a
{0,1,3,5}
而
{0,1,3,5}
既不属于
{0}
，也不属于
{0}
，所以得到新分划
Π1
：
{0}
，
{4}
，
{1,2,3,5}
对
{1,2,3,5}
进行审
查：
∵
{1,5} b
{2,3} b
5}
，
{2,3}
{1, 5} a
{2,3} a
{4}
{1,2,3,5}
，故得到新分划
Π2
：
{0}
，
{4}
，
{1,
{1, 5}
{1,3}
，故状态
2
和状态
3
不等价，得到新分划
Π3
：
{0
}
，
{2}
，
{3}
，
{4}
，
{1, 5}
这是最后分划了
最小
DFA
：
第
5
题
构造一个
DFA
，它接收
Σ={0,1}
上所有满足如下条件的字符串：每
个
1
都有
0
直接跟在
右边。并给出该语言的正
规式。
答案：
按题意相应的正规表达式是
(0*1
0)*0*
，或
0*(0 |
10)*0*
构造相应的
DFA
，首先构造
NFA
为
用子集法确定化：
I
{X,0,1,3,Y} {0,1,3,Y}
{2}
{1,3,Y}
重新命名状态集：
I0
{0,1,3,Y}
{0,1,3,Y}
{1,3,Y}
{1,3,Y}
I1
{2}
{2}
{2}
3
百度文库
-
让每个人平等地提升自我
S
1
2
3
4
DFA
的状态图：
0
2
2
4
4
1
3
3
3
可将该
DFA
最小化：
终态组为
{1,2,4}
，非终态组为
{3}
，
{1,2,4}0
{1,2,4}
，
{1,2,4}1
{3}
，所以
1,2,4
为等价状
态，可合并。
第６题
设无符号数的正规式为
θ：
θ=dd*|dd*.dd*|.dd*|dd*10(s|
ε
)dd*
|
10(s|ε
)dd*|
.
d
d*
10(s|ε
)dd*
|dd*
.
dd*
10(s|ε
)dd*
化
简
θ，画出
θ
的
DFA
，其中
d={0,1,2,…,9}，
s={
＋，－
}
答案：
先构造
NFA
：
d
.
X
用子集法将
NFA
确定化：
d
A
ε
1
0
F
B
d
d
s
C
G
10
D
E
d
d
Y
ε
s
ε
d
H
d
3
百度文库
-
让每个人平等地提升自我
X
T
0
=XA
B
F
A
T
1
=B
C
T
2
=FG
G
H
T
3
=A
T
4
=C
D
T
5
=G
T
6
=H
T
7
=DE
E
Y
T
8
=E
T
9
=Y
将
<
/p>
XA
、
B
、
FG
、
A
、
C
、
G
、
H
、
DE
、
E
、
Y
重新命名，分别用
0
、
1
、
2
、
3
、
4
、
5
、
6
、<
/p>
7
、
8
、
9
表示。终态有
0
、
3
、
4
、
6
、
9
。
0
1
2
·
1
s
5
10
2
d
3
4
6
ε
XA
B
FG
A
C
G
H
DE
E
Y
·
B
B
s
G
E
10
F
F
D
d
A
C
H
A
C
H
H
Y
Y
Y
3
百度文库
-
让每个人平等地提升自我
3
4
5
6
7
8
9
1
DFA
的状态图：
8
2
7
3
4
6
6
9
9
9
d
·
·
d
1
1
0
s
d
d
6
d
4
1
0
7
s
0
d
2
5
d
9
d
8
d
1
0
3
d
第
7
题
给文法
G[S]
：
S
→
aA|bQ
A→aA|bB|b
B→bD|aQ
Q
→
aQ|bD|b
D→bB|aA
E→aB|bF
F
→
bD|aE|b
构造相应的最小的
DFA
。
答案：
3
百度文库
-
让每个人平等地提升自我
先构造其
NFA
：
S
A
Q
BZ
DZ
D
B
0
1
2
3
4
5
6
a
b
S
b
a
Q
a
b
D
b
a
A
a
b
B
a
b
E
Z
b
b
b
b
a
F
用子集法将
NFA
确定化：
a
A
A
Q
Q
A
A
Q
b
Q
BZ
DZ
D
B
B
D
将
S
、
A
、
Q
、
BZ
、
DZ
、
D
、
B
重新命名，分别用
0
、
1
、
2
、
3
、
4
、
5
、
6
表示。因为
3
、
4
中含有
z
，所以它们为终态。
a
1
1
2
2
1
1
2
DFA
的状态图：
b
2
3
4
5
6
6
5
3
百度文库
-
让每个人平等地提升自我
a
a
0
a
b
b
2
a
a
a
b
6
b
4
b
3
1
b
5
b
最小化为：
a
令
P
0
＝（
｛
0,1,2,5,6
｝
,
｛
3,4
｝
）用
< br>b
进行分割：
P
1
＝（
｛
0,5, 6
｝
,
< br>｛
1,2
｝
,
< br>｛
3,4
｝
）再用
b
进行分割：
P
2
＝（<
/p>
｛
0
｝
,
｛
5, 6
｝
,
｛
1,2
｝
,
｛
3,4
｝
）再用
a
、
b
进行分割，仍不变。
再令｛０｝为
A
，
｛
1
，
2
｝为
B
，
｛
3
，
4
｝为
C
，
｛
5
，
6
｝为
D
。
a
第８题
S
→
0A|1B
A→1S|1
B→0S|0
答案：
a , b
A
a
b
a
B
b
D
b
C
给出下述文法所对应的正规式：
3
百度文库
-
让每个人平等地提升自我
解方程组
S
的解：
S=0A|1B
A=1S|1
B=0S|0
将
A
、
B
产生式的右部代入
S
中
S=0
1S|01|10S|10=
（
01|10
）
S|
（
01|10
）所以：
S=
(01|10)*(01|10)
第
9
题
将下图的
DFA
最小化，并用正规式描述它所识别的语言。
答案：
最小化为：
c
b
a
1
3
c
b
d
5
6
b
b
2
b
a
4
d
a
b
7
令
P
0
＝（
｛
1,2,3,4,5
｝
,
｛
6,7
｝
）用
b
进行分割：
P
1
＝
（
｛
1,2
｝
,
｛
3,4
｝
,
｛
5
｝
,<
/p>
｛
6,7
｝
）再
用
a
、
b
、<
/p>
c
、
d
进行分割
，仍不变。
再令｛
1,2
｝为
A
，
｛
3
，
< br>4
｝为
B
，
｛
5
｝为
C
，
｛
6
，
7
｝为
D
。
c
3
百度文库
-
让每个人平等地提升自我
b
a
A
a
B
d
C
b
r=b
*
a(c|da)
*
< br>bb
*
=b
*
< br>a(c|da)
*
b
+
3
D
b
百度文库
-
让每个人平等地提升自我
附加题
问题
1
：
为下边所描述的串写正规式，字母表是
{a,b}.
a)
以
ab
结尾的所有串
b)
包含偶数个
b
但不含
a
的所有串
c)
包含偶数个
b
且含任意数目
a
的所有串
d)
只包含一个
a
的所有串
e)
包含
ab
子串的所有串
f)
不包含
ab
子串的所有串
答案：
注意
正规式不唯一
a)
(a|b)*ab
b)
(bb)*
c)
(a*ba*ba*)*
d)
b*ab*
e)
(a|b)*ab(a|b)*
f)
b*a*
问题
2
：
请描述下面正规式定义的串
.
字母表
{0
，
1}.
a)
0*(10
+
)*0*
b)
(0|1)*(00|11) (0|1)*
c)
1(0|1)*0
答案：
a)
每个
1
至少有一个
0
跟在后边的串
b)
所有含两个相继的
0
或两个相继的
1
的串
c)
必须以
1
开头和
< br>0
结尾的串
问题
3
：
构造有穷自动机
.
a)
构造一个
DFA
，接受字母表
b)
构造
一个
DFA
，接受字母表
c)
构造
一个
NFA
，接受字母表
{0,
1}
上的以
01
结尾的所有串
{0, 1}
上的不包含
01
子串的所有串
.
{x,y}
上的正规式
x(x|y)
*x
描述的集合
3
百度文库
-
让每个人平等地提升自我
d)
构造一个
NFA
，接受字母表
等价的
DFA.
以及最小状态
DFA
答案：
{a, b}
上的正规式
(ab|a)*b+
描述的集合并将其转换为
b)
c)
3
百度文库
-
让每个人平等地提升自我
最小化的
DFA
问题
4
：
设有如图所示状态转换图，求其对应的正规表达式。
可通过消结法得出正规式
R=(01)*((00|1)(0|1)*|0)
也可通过转换为正则文法，解方程得到正规式。
问题
5
：
3
百度文库
-
让每个人平等地提升自我
已知正规式：
(1)((a|b)*|aa)*b;
(2)(a|b)*b.
试用有限
自动机的等价性证明正规式
(1)
和
(
2)
是等价的，并给出相应的正规文法。
分析：
基
本思路是对两个正规式，分别经过确定化、最小化、化简为两个最小
< br>DFA
，如这两
个最小
DFA
一样，也就证明了这两个正规式是等价的。
答案：
状态转换表
1
X124
1234
124Y
状态转换表
2
1
2
3
1
a
2
2
2
a
2
B
3
3
3
b
3
a
1234
1234
1234
b
124Y
124Y
124Y
由于
2
与
3
完全一样，将两者合并，即见下表
3
百度文库
-
让每个人平等地提升自我
2
3
而对正
规式
(2)
可画
NFA
图，如图所示。
X12
12
12Y
a
12
12
12
b
12Y
12Y
12Y
可化简得下表
1
2
a
2
2
b
3
3
得
DFA
图
两图完全一样，故两个自动机完全
一样，所以两个正规文法等价。
对
相应正规文法
,
令
A
对应
1
，
B
对应
2
故为：
A
→
aA|bB|b
B
→
aA|bB|b
即为
S
→<
/p>
aS|bS|B,
此即为所求正规文
法。
问题
6
：考虑正规表达式
r = a*b(a | b)
，构造可以生成语言
L(r)
的一个正规文法。
答案：
3
百度文库
-
让每个人平等地提升自我
S
→
a*b(a | b)
变换为
S
→
aA, S
→
b(a | b) , A
→
aA , A
→
b(a | b)
变换为
S
→
aA, S
→
bB, B
→
(a | b) , A
→
aA , A
→
bC, C
→
(a | b)
变换为
S
→
aA, S
→
bB, B
→
a, B
→
b , A
→
aA , A
→
bC, C
→
a, C
→
b
所以，一个可能的正规文法为
G[S]
：
S
→
aA, S
→
bB, B
→
a, B
→
b , A
→
aA , A
→
bC, C
→
a, C
→
b
或表示为：
S
→
aA | bB, B
→
a | b , A
→
aA | bC, C
→
a | b
（适当等价变换也可以，但要作说明，即要有步骤）
问题
7
：
考虑下图所示的
NFA
N
，构造可以生成语言
L(N)
的一个正规文法。
答案：
G[P]:
P
→
0
P
?
1 P
?
1 Q
3
百度文库
-
让每个人平等地提升自我
Q
→
0
R
?
1 R
R
→
ε
问题
8
：考虑如下文法
G[S]
：
S
→
0S
?
1S
?
1A
A
→
0B
?
1B
B
→
ε
a)
试构造语言为
L(G)
的一个正规表达式。
b)
试构造语言为
L(G)
的一个有限自动机。
答案：
a)
由
A
→
0B
，
B
→
ε
得
A
→
0
由
A
→
1B
，
B
→
ε
得
A
→
1
由
A
→
0
，
A
→
1
得
A
→
0
?
1
由
S
→
1A
，
A
→
0
?
1
得
S
→
1( 0
?
1 )
由
S
→
1A
，
A
→
0
?
1
得
S
→
1( 0
?
1 )
由
S
→
0S
，
S
→
1( 0
?
1 )
得
S
→
0*1( 0
?
1 )
由
S
→
1S
，
S
→
1( 0
?
1 )
得
S
→
1*1( 0
?
1 )
由
S
→
0*1( 0
?
1
)
，
S
→
1*1( 0
?
1 )
得
S
→
0*1( 0
?
1 )
?
1*1( 0
?
1 )
所以，一个可能的正规表达式为：
0*1( 0
?
1 )
?
1*1( 0
?
1 )
b)
3
百度文库
-
让每个人平等地提升自我
3