形式语言与自动机答案蒋宗礼
【篇一：形式语言第四章参考答案(蒋宗礼)】
p> 解：所求正则表达式为：(0+1)*。
+
⑵ {0, 1}。
解：所求正则表达式为：(0+1)+。
⑶ { x│x∈{0,1}且x中不含形如00的子串 }。
解：根据第三章构造的fa，可得所求正则表达式为：
1*(01+)*(01+0+1)。⑷ { x│x∈{0,1}*且x中不含形如00的子串 }。 +
+ +
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
q4：设x=5n+4。输入0，x=(5n+4)*2=10n+8，模5是3，故进入
q3
输入1，x=(5n+4)*2+1=10n+9，模5是4，故进入q4 则状态转移
图如下：
则所求的正则表达式为：
1(010*1+(1+001*0)(101*0)*(0+110*1))*(1+001*0)(101*0)* ⑻
{ x│x∈{0,1}+ 且x的第10个字符是1 }。解：所求正则表达式为：(0+1)1(0+1)*。
⑼ { x│x∈{0,1}+ 且x以0开头以1结尾 }。
解：所求正则表达式为：0(0+1)*1。
⑽ { x│x∈{0,1}+ 且x中至少含两个1 }。解：所求正则表达式为：(0+1)*1(0+1)*1(0+1)*。
⑾ { x│x∈{0,1}*和如果x以1结尾，则它的长度为偶数；如果x以
0结尾，则它的长度为奇数}。解：所求正则表达式为：
(0+1)2n+11+(0+1)2n0 (n∈n)
或0+(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)*。
9
***************************************************************************** ****
2.理解如下正则表达式，说明它们表示的语言
（1）(00+11)+表示的语言特征是0和1都各自成对出现（2）
(1+0)*0100表示的语言特征是以010后接连续的0结尾（3）
(1+01+001)*(?+0+00) 表示的语言特征是不含连续的3个0
（4）((0+1)(0+1))*+ ((0+1)(0+1)(0+1))* 表示所有长度为3n或2m
的0，1串（n?0,m?0）（5）((0+1)(0+1))* ((0+1)(0+1)(0+1))* 表示所有长度为3n+2m的0，1串（n?0,m?0）（6）00+11+（01+10）（00+11）*（10+01）表示的语言特征为长度为偶数n的串.当n=2时，是00或11的串。
+
n?4时，是以01或10开头，中间的子串00或11成对出现，最后
以10或01结尾的串
***************************************************************************** **************** 4.3.证明下列各式褚颖娜 02282072
（1）结合律 (rs)t=r(st) (r+s)+t= r+(s+t)
1）证明对? x∈(rs)t 总可以找到一组x1 x2 x3 使得 x=x1x2x3 其
中x3∈t x1x2∈rs 且 x1∈r, x2∈s,
则 x2x3∈st 因此x1(x2x3)∈r(st) 即 x1x2x3∈r(st)x∈r(st)得证因此 (rs)t?r(st) 同理可证r(st)? (rs)t 则 (rs)t=r(st) 成立
2) 证明对?x∈(r+s)+t x∈(r+s)或x∈t 对于x∈r+s?x∈r或r∈s ，因此x∈r或x∈s或x∈t?x∈r或x∈(s+t) ? x∈r+(s+t) 所以
(r+s)+t? r+(s+t) 同理可证r+(s+t)? (r+s)+t 则(r+s)+t= r+(s+t) 成立（2）分配律 r(s+t)=rs+rt (s+t)r=sr+tr
1) 证明对于?x∈r(s+t) 总可以找到x1 x2 使得x=x1x2 其中x1∈r, x2∈（s+t）
由x2∈（s+t）? x2∈s或x2∈t
则x1x2∈rs或x1x2∈rt 所以r(s+t)?rs+rt
对于?x∈rs+rt ?x∈rs或x∈rt 且总可以找到一组x1 x2 使得
x=x1x2 其中x1∈r, x2∈s或x1∈r, x2∈t?x1∈r，x2∈s或x2∈t? x1∈r，x2∈(s+t)? x1x2∈r(s+t) 所以rs+rt?r(s+t) 则r(s+t)=rs+rt
2) 证明对于?x∈(s+t)r 总可以找到x1 x2 使得x=x1x2 其中 x1∈
（s+t），x2∈r
由x1∈（s+t）? x1∈s或x1∈t
则x1x2∈sr或x1x2∈tr 所以(s+t)r?sr+tr
对于?x∈sr+tr ?x∈sr或x∈tr 且总可以找到一组x1 x2 使得
x=x1x2 其中x1∈s, x2∈r或x1∈t, x2∈r? x1∈s或x1∈t, x2∈r? x1∈(s+t) ,x2∈r? x1x2∈(s+t)r 所以sr+tr ?(s+t)r
则(s+t)r=sr+tr
(3)交换律 r+s=s+r
证明对于 ?x∈r+s?x∈r或x∈s?x∈s或x∈r?x∈s+r 所以
r+s?s+r 同理可证s+r∈r+s
则r+s=s+r （4）幂等律 r+r=r
证明对于 ? x∈r+r? x∈r或x∈r? x∈r 所以r+r?r
对于 ?x∈r?x∈r或x∈r?x∈r+r 所以r?r+r 因此 r+r=r
（5）加法运算零元素：r+?=r
证明对于 ? x∈r+?? x∈r或x∈?? x∈r 所以r+??r
对于 ?x∈r?x∈r或x∈??x∈r+? 所以r?r+? 因此 r+?=r
(7)乘法运算零元素：r?=?r=? 证明：∵对?x?r
x?=?x=?∴r{?}={?}r=r
∴r?=?r=?
*
由第一章的作业1.30中的第八题 (l2∪l1)*=( l2* l1*)* 其中l1、l2 为正则语言
又r、s为正则表达式正则语言可以用正则表达式表示，因此显然有(r+s)*= (r*s*)*成立即(r*s*)*=(r+s)*
成立
(11) (r*)*=r*
由第一章的作业1.30中的第三题 (l1*)*= l1*其中l1为正则语言
又r为正则表达式正则语言可以用正则表?达式表示，因此显然有(r)= r成立
**
**
*
*
*
*
*
***************************************************************************** ****
4下面各式成立吗？请证明你的结论 (1) (r+rs)*r=r(sr+r)* 证明：成立。
如果对所有的k=0, (r+rs)k r=r(sr+r)k 成立，则(r+rs)*r=r(sr+r)*肯定成立可以用归纳法证明(r+rs)k r=r(sr+r)k对所有的k=0成立
i. k=0时候，(r+rs)0 r=r= r(sr+r)0
nn
ii. 假设k=n时候(r+rs)r=r(sr+r)成立，往证k=n+1时候结论成立(r+rs)n+1r=(r+rs)n (r+rs)r=(r+rs)n (rr+rsr)= (r+rs)n r (r+sr)=
r(sr+r)n (r+sr)
= r(sr+r)(sr+r)= r(sr+r)
这就是说，结论对k=n+1成立，即证明了(r+rs)k r=r(sr+r)k对所有的k=0成立，所以(r+rs)*r=r(sr+r)* (2) t(s+t)r=tr+tsr
证明：不成立。不妨取r=0,s=1,t=2,则t(s+t)r=2(1+2)0=210+230,但tr+tsr=20+210. (3) rs=sr
证明：不成立。不妨取r=0,s=1,显然rs=01,而sr=10.
(4) s(rs+s)*r=rr*s(rr*s)*
不成立，假设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)*,
结论不成立 (5)(r+s)*=(r*s*)* 证明：结论成立。
i. l(r+s)=l(r)?l(s), l(r)=l(rs0)?l(r*s*), l(s)=l(r0s)?l(r*s*) 那么
l(r+s)=l(r)?l(s) ?l(r*s*)，(l(r+s))* ?(l(r*s*))*,
n
n+1
l((r+s)*) ?l( (r*s*)* ),所以(r+s)* ? (r*s*)* ii. (r+s)*= ((r+s)*)*,
对任意m,n=0,rmsn ?(r+s)m+n ，所以r*s*?(r+s)*
(r*s*)*?((r+s)*)*= (r+s)*
由i，ii可以知道(r*s*)*?(r+s)*，(r+s)* ? (r*s*)* 得到(r+s)*=(r*s*)*
(6)(r+s)*=r*+s*
不成立，假设r,s分别是表示语言r，s的正则表达式，例如当r={0}，s={1},l((r+s)*)={x| x=?或者x是所有由0,1组成的字符串}
l(r*+s*)=l(r*)?l(s*)={?,0,00,000,……}?{?,1,11,111,……} l((r+s)*) ? l(r*+s*),例如10? l((r+s)*),10? l(r*+s*)
***************************************************************************** ***************** 5.构造下列正则表达式的等价fa 吴丹02282090
?1??0?1?
?
??0?11?
?
?2?00?0?1???01?
?
?
?01000
?
【篇二：形式语言与自动机的关系】
txt>新疆师范大学数理信息学院数学03-6班
摘要：
形式语言的直观意义，自动机的直观意义，形式语言的定义，
形式语言的特征，语法的分类，自动机的定义，自动机的分
类，各种自动机的定义，形式语言和自动的的关系，自动机
的对语言的例子
基本关键词：
形式语言的定义；自动机的定义；形式语言和自动机的关系
1，形式语言的直观意义
直观地讲，形式语言是用来精确描述语言和它结构的手段。它一重
写规则???的
?,?均为字符串。形式来表示，其中，重写规则就是在包含?的字符
穿中遇见规则左边的
?时，?部分重新写为右边的?。这样一个初设的字符串通过不断地
运用重写规
则，就可以到另一个字符串。通过选择不同的规则并且以各种不同
的顺序来运用最这些规
则，如果指
定一个初始符，某规则以其为左部，一组规则就可以构成一个语法。 2，形式语言的定义
形式语法是一个四元组g=（n, v, p, s）,其中n是非终结符的有限集合，有时也称变量，它们相当于各种句法范畴。v是终结符的有限集合，若语法生成的是自然语言，这些终端语符就相当于这种语言中
具体的词，终端语符集这种语言的词库，p是以重写规则的有限集合，基本形式p?????，即?改写为?，其中箭头表示指令，一条规
则就是一个机械性的操作程序，用来演算它联系着的两侧语符集或
语符序列之间的关系，而s是一个特定的初始符；
3，语法的分类
乔姆斯在他的著名【文章】中根据重写规则将语法分成四类：正则
语法，上下文有关语法，上下文无关语法；有这些语法生成的语言
是正则语言，，上下文有关语言，上下文无关语言，递归数集合。
a 如果p中的规则，满足如下的形式：a?bx或，a?x，其中，a,b
是非终结符，x是终结符，则g称为正则语法（简称为fsg）。
b 如果p中的规则，满足如下的形式：a??,其中，a是非终结符, ?
是由n和v中字符所组成的字符串（或可表示为???n?v??,?意味着它右边的字符可以重复0到任何多次），则g称为上下文无关语法（简称为cfg）。
d如果p中的规则，满足如下的形式：?a?????,其中，a是非终结符,?,?,?,是字符串，且?至少包含一个字符，则g称为上下有无关语
法（简称为csg）。
d如果p中的规则，满足如下的形式：其中，?，?是字符串，则g
称为无限制重写系统。
对于以上任何一种语法，两个字符串之间一次派生关系?可定义为：如果x?y是p中的规则，?x???y?。
字符串?，?有多次派生关系?则是说，通过多次应用一次派生关系，从?可派生出*
?，并记为???： *
???0,???n，而对i?0,....n?1,?i??i?n。
给定以语法，其语言定义为所有合法终结字符串的集合。合法终结
字符串是指由初始符s出发，运用重写规则而派生得终结字符串，即，
l?g?????v;s??**?
*例子：假设g=(n, v, p, s), n={s, a} , v={0, 1},
p={s?a1,a?a0,a?0} 则，l(g)??0m?1?是正则语法，在v={0, 1}上
它所对应的正则表达式是001。 m
形式语言的特征：
⑴高度抽象化（采用形式化的手段，专用符号，数学公式来描述语
言的，结构关系，这种关系是抽象的）。
4，自动机的直观意义
解决一个数学上的难题，后来又被试图模仿人的感觉和思维。自动
机有非常简的部件和操作组成：输入/输出带时用来存放输入字符串
以及输出字符（它们可以时同一带，也可以是不同一条带），读/写
头用来阅读输入/输出带上目前所处理的字符及位置，在带上写下一
个字符，并可以在带上向左或向右移动一个位置，让读/读写头做出
相应的操作，改变自己的状态，并最终决定是否接受输入字符串为
合法。当给定以字符串时，自动机通过自己的读/写头扫描，修改这
一字符串，并改变自己的状态。如果自动机顺利地进入终止状态，
且输入/输出带满足一定的条件，我们称自动机接受这一字符串。这
个过程称为识别。
5，自动机的定义
5.1定义：确定有限自动机是以个七元组m??q,i,u,?,?,q,f?,其中
q??ss是自动机内部状态?，且q是有限集合 i??是输入字符?，且i是有限集合
u??uu是输出字符?，且u是有限集合
?是定义域为 q?i，值域为q的状态转移函数 ?
?是定义域为 q?i，值域为u
q为初始状态的有限集合
f?q为终止状态
给定一字符串 a?a0a1...an初始时，有限自动机m处于状态q0，从a0开始，根据状态转移函数?转移到另一状态q1??(q0,a0)，根据输出函数?在一输出带上印出字符??q0,a0?，并将读/写头在输入/输出带上各向右移动一格。此时，m便处于状态q1，读字符a1。重复以上步骤，一直到m读完an，如果，m处于某中移终止状态，即f的一个元素，那么，我们就称m接受字符串a；否则，m读完an但不处于任一终止状态，或者，在其过程中?没有定义，我们称m不接受字符串a。
由m 定义的语言t?m?就是被m接受的字符串全集
5.2定义：下推自动机是一个m??q,?,?,?,q0,z0,f?,其中 q?ss是一个内部状态?，且q是有限集合 ?
???uu是输入带上字符?，且?是有限集合
???uu是栈上字符?，且 ?是有限集合
q0?q为初始状态
z0?? 为栈中一个特殊符号，表明栈底
f?q为终止状态集
?是定义域为q??????????,值域为q??* 的有穷子集的状态转移映照。
5.3定义：图灵机是一个七元组 m??q,?,?,?,?,q0,f?,其中
q?ss是一个内部状?，且q是有限集合态
，且?符???uu是输入带上字?是有限集合 ?
?????b?,b表示空白字符；
?是定义域为q??,值域为q????r,l,s?转移函数，r, l 和 s 分别指右移一格，左移一格以及停止不动；
—属于q-i的空格元素
q0为初始状态；
f?q为终止状态集
给定字符串a，存放域它的输入/输出带上，开始时，m处于状态
q0，它的读/写头扫描着a的最左字符。根据转移函数?的定义，即
对于目前状态及正扫描着的字符，m 改变当前状态，读/写头扫描的
字符，以及读/写头的位置。重复这个步骤直至m进入某一终止状态；或者，在其过程中?没有定义，即m停止工作。前者称之为m接受
字符串a，后者称之为m不接受字符串a。
严格地讲，我们对于m的每个情况，定义格局为（q，a，i），这里，q?q,a是字符串，i是整个数，表示读/写头相对于a左端的距离。图灵机m通过如下转移动作引起格局变化；
假设?q,a1a2....an,i?,1?i?n?1是当前m的格局，
如?p,a,r????q,ai?,1?i?n,则
?q,a1a2....an,i?m?q,a1a2....ai?1aai?1....an,i?1?
即m的读/写头在i位置上原来的ai就消失了，并且读/写头向右移
动一格，从i变化为i?1。
如果?p,a,l????q,ai?,2?i?n,则，
?q,a1a2...an,i?m?q,a1a2...ai?1aai?1...an,i?1?
即m的读/写头在i位置上原来的ai就消失了，并且读/写头向左移
动一格（从i变化为i-1）；
当i=n+1，即m的读/写头超出原字符串的右端，注释空白符时，如果?p,a,r????q,b?,则，
?q,a1a2...an,n?1?m?q,a1a.2..ana,n?2?如果?p,a,l????q,b?,
则 ?q,a1a2...an,n?1?m?q,a1a2...ana,n?。
对两个格局x,y，如果xmy，称y是由通过一次动作而得。如果，y
是由x通过次?*
_
数动作而得，则记为
由图灵机m接受的语言则定义为：t?m???aa??*,?q0,d,1?
5.4定义：线性带线自动机是一个七元组m??q,?,?,?,?,q0,f?,其中q??ss是自动机的内部状态?，且，q是有限集合 ???uu是输入带
上字符?，且?
?????b?,b表示空白字符；是有限集合
?是定义域为q??,值域为q????r,l,s?转移函数，r, l 和 s 分别指右
移一格，左移一格以及停止不动；
—属于q-i的空格元素；
q0为初始状态；
f?q为终止状态集
【篇三：形式语言与自动机教学提纲】语言与自动机课程提纲