形式语言与自动机.doc

形式语言与自动机（计算机网络班）
第一章 绪论
1. 幂集
2. 字母表的性质
3. 真前缀、真后缀、前缀、后缀
4. 语言的形式化表示
题目：
填空题
{Φ,{Φ}}的幂集是：{Φ,{Φ},{{Φ}},{Φ,{Φ}}}
判断题
对于任何一个非空集合A, A2A 错误
{a,d,f}{a,b,c,…,z}是字母表 正确
ε一定是字符串的前缀或后缀，当字符串不为ε时，则ε一定是其真前缀或真后缀 正确
∑={aa,ab,bb,ba}，求字符串aaaaabbbba的所有前缀的集合、后缀的集合、真前缀的集合、真后缀的集合
解：
由前缀、后缀、真前缀、真后缀的集合可以有：
其前缀集合为：{ε,aa,aaaa,aaaaab,aaaaabbb,aaaaabbbba}
其真前缀集合为：{ε,aa,aaaa,aaaaab,aaaaabbb}
其后缀集合为：{ε,ba,bbba,abbbba, aaabbbba, aaaaabbbba }
其真后缀集合为：{ε,ba,bbba,abbbba, aaabbbba}
设，请给出上的下列语言的形式表示。
所有最多有一对连续的0或者最多有一对连续的1的串。
解答：。
所有最多有一对连续的0并且最多有一对连续的1的串。
解答：按照实际情况分成4类：
1) 只有一对连续的0： 。
2) 只有一对连续的1： 。
3) 没有连续的0并且没有连续的1：。
4) 有一对连续的0和一对连续的1：
。
所有长度为偶数的串。
解答：
所有倒数第10个字符是0的串。
解答：{0,1}0{0,1}。
第二章 正则文法
G=(V,T,P,S)
1. 文法产生句子用到的是推导，判断一个句子的合法性可以使用产生语言文法的推导和规约进行判断
2. 文法的构造。由给出的语言构造相应的文法，没有太直接的方法。
常见的文法构造：
L（G）={ xn |n>=1} G: S→x|xS
L（G）={ xn |n>=0} G: S→xS|ε
L（G）={ xn yn|n>=1} G: S→xSy|xy
L（G）={ xn yn|n>=0} G: S→xSy|ε
重要结论：对于任意字母表∑，当要产生语言∑+时，只用在文法中对∑的每一个符号a安排如下形式的产生式就可以：S→a|As
题目：
设文法G的产生式集如下，试给出句子aaabbbccc的至少两个不同的推导和至少两个不同的归约
S→aBC|aSBC
aB→ab
bB→bb
CB→BC
bC→bc
cC→cc
解：推导一：
S→aBC|aSBC
aB→ab
S=>aSBC
=>aaSBCBC
=>aaaBCBCBC
=>aaabCBCBC
=>aaabBCCBC
=>aaabbCCBC
=>aaabbCBCC
=>aaabbBCCC
=>aaabbbCCC
=>aaabbbcCC
=>aaabbbccc
推导二：
S=>aSBC
=>aaSBCBC
=>aaaBCBCBC
=>aaaBBCCBC
=>aaaBBCBCC
=>aaabbCBCC
=>aaabbBCCC
=>aaabbbCCC
=>aaabbbcCC
=>aaabbbccc
归约一、归约二分别为推导一和推导二的逆过程
设，构造下列语言的文法。

G: S →aAB|aSAB
BA→AB
aB→ab
bB→bb
bA→ba
aA→aa

G: S→aWa
W→aW|bW|cW|a|b|c

G:

G:
出现错误

第三章 有穷状态自动机
1. 根据语言构造FA
2. 根据NFA，构造与之等价的DFA(构造过程见P109)
3. 根据文法构造相应的FA
题目：
{x|xÎ{0，1}+且当把x看成二进制时，x模5和3同余，要求当x为0时，|x|=1,且x¹0时，x的首字符为1 }试构造相应的DFA
1. 以0开头的串不被接受，故设置陷阱状态，当DFA在启动状态读入的符号为0，则进入陷阱状态
2. 设置7个状态：开始状态qs,q0:除以5余0的等价类，q1：除以5余1的等价类,q2:除以5余2的等价类，q3:除以5余3的等价类，q4:除以5余4的等价类，接受状态qt
3. 状态转移表为
状态
0
1
q0
q0
q1
q1
q2
q3
q2
q4
q0
q3
q1
q2
q4
q3
q4

{x|xÎ{0，1}*且如果x以1结尾，则它的长度为偶数；如果x以0结尾，则它的长度为奇数}
可将{0，1}*的字符串分为4个等价类。试分别构造相应的DFA和NFA
DFA构造:
q0： [e]的等价类，对应的状态为终止状态
q1:x的长度为奇且以0结尾的等价类
q2：x的长度为奇且以1结尾的等价类
q3: x的长度为偶且以0结尾的等价类
q4: x的长度为偶且以1结尾的等价类

NFA构造：

根据给定的NFA，构造与之等价的DFA(略，详见前一位同学的题目)
根据下列给定文法，构造相应的FA。
(1) 文法G1的产生式集合如下：
G1: S→a|Aa
A→a|Aa|cA|Bb
B→a|b|c|aB|Bb|Cb
(2) 文法G2的产生式集合如下：
G2: S→a|Aa
A→a|Aa|Ac|Bb
B→a|b|c|Ba|Bb|Bc

解答: 文法G1对应的FA如下所示

文法G2对应的FA如下所示
第四章 正则表达式
1. 根据语言给出相应的正则表达式
2．根据正则表达式构造等价FA
3. 根据DFA构造等价的正则表达式
题目：
判断题：
r,s是字母表∑上的正则表达式
①r+e=r
②(rs)n=rnsn
③rs=sr
以上都是错误的
填空题
语言Φ的正则表达式是：Φ
语言{ε}的正则表达式是：ε
写出表示下列语言的正则表达式。
{ x│x∈{0,1}+ 且x的第10个字符是1 }。
解：所求正则表达式为：(0+1)91(0+1)*。
{ x│x∈{0,1}*和如果x以1结尾，则它的长度为偶数；如果x以0结尾，则它的长度为奇数}。
解：所求正则表达式为：(0+1)2n+11+(0+1)2n0 (n∈N)
或(0+1)((0+1)(0+1))*1+(0+1)(0+1)((0+1)(0+1))*0。
{ x│x是十进制非负实数 }。
解：首先定义∑＝{ .,0,1,2,3,4,5,6,7,8,9}
则所求正则表达式为：(0+1+…+9)*. (0+1+…+9)*。
根据正则表达式构造FA和根据FA构造正则表达式略（参前一位同学）
第五章 正则语言的性质
就一题（参前一位同学）
补：

构造等价于下图所示DFA的正则表达式。
S
q1
q0
q2
q3
1
0
0
0
1
1
1
0

答案(之一)：( 01+(1+00)((1+00*1)0)*((1+00*1)1) )* (e+(1+00)((1+00*1)0)*00*)
q1
q0
q2
q3
1
0
0
0
1
1
1
0
e
e
X
Y
e

预处理：

去掉q3：
q1
q0
q2
1
0
1
1+00*1
0
e
X
Y
e
00*

去掉q1：
q0
q2
1+00
(1+00*1)0
e
X
Y
e
00*
(1+00*1)1
01

q0
e
X
Y
e+(1+00)((1+00*1)0)*00*
01+(1+00)1+00*1)0)*((1+00*1)1)
去掉q2：

去掉q0：

X
Y
(01+(1+00)((1+00*1)0)*((1+00*1)1))* (e+(1+00)((1+00*1)0)*00*)

1、 设∑={ a,b },求字符串aaba的所有前缀、真前缀、后缀、真后缀。
解： 前缀：εa,aa,aab,aaba
真前缀：ε，a,aa,aab
后缀：ε，a,ba,aba,aaba
真后缀：ε，a,ba,aba
2、 设∑={ 0,1 },请给出∑上的下列语言的文法：
(1) 所有含有3个连续0的串。
解：S>A000A
A->0A|1A|ε
(2) 至少有3个0的串
解：S->A0A0A0A
A->0A|1A|ε
3、 简单描述由下面的产生式对应的文法生成的语言。
（1）S->Ab
A->aAb
A->ε
解：L={ anbn+1|n≥0 }
(2) S->aA
A->bS
S->ε
解：L={ （ab）n|n≥0}
4、 构造识别下列语言的DFA.
(1) L={ x000|x∈{ 0,1 }* }

(2)L={ x|x∈{ 0,1 }*且x中不含形如00的子串}

5、 构造识别下列语言的NFA
(1) { x|x∈{ 0,1 }+,x能整除2 }

(2) 构造一个3个状态的NFA,接受的语言{ ab,abc}*

6、 构造识别语言L((a+b)*b(a+bb)*)的NFA。

7、 给出下图自动机接受的语言的正则表达式。

①
②
去掉q1

③ 去掉q2

④ 去掉q0

所以该自动机接受的语言的正则表达式为：(ab+(aa+b)(ba)*bb)*
8、 证明L={ aN!|n≥0 }不是RL.
证明：取z=aN!,u=aj,v=ak,w=aN!-j-k
uvw= aj(ak)iaN!-j-k
=aN!+（i-1）k
取i=2
N!+(i-1)k=N!+k
又k≤N
故N!+k不是一个数的阶乘
所以aN!+（i-1）k∈L
所以L={ aN!|n≥0 }不是RL.