文档库

最新最全的文档下载
当前位置:文档库 > 形式语言与自动机蒋宗礼答案

形式语言与自动机蒋宗礼答案

形式语言与自动机蒋宗礼答案

【篇一:形式语言第四章参考答案(蒋宗礼)】

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,自动机的直观意义

,如果说语法时用来精确描述语言的和它的结构,那么自动机便是

用来机械地刻画对输入字符串的处理过程。最初,自动机(automation)得得提出时用来解决一个数学上的难题,后来又被

试图模仿人的感觉和思维。自动机有非常简的部件和操作组成:输

入/输出带时用来存放输入字符串以及输出字符(它们可以时同一带,也可以是不同一条带),读/写头用来阅读输入/输出带上目前所处理

的字符及位置,在带上写下一个字符,并可以在带上向左或向右移

动一个位置,让读/读写头做出相应的操作,改变自己的状态,并最

终决定是否接受输入字符串为合法。当给定以字符串时,自动机通

过自己的读/写头扫描,修改这一字符串,并改变自己的状态。如果

自动机顺利地进入终止状态,且输入/输出带满足一定的条件,我们

称自动机接受这一字符串。这个过程称为识别。

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是有限集合 ?

u是输入带上字符?,且?是有限集合

???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为终止状态集

【篇三:形式语言与自动机教学提纲】语言与自动机课程提纲