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

内容发布更新时间 : 2024/12/22 20:07:01星期一 下面是文章的全部内容请认真阅读。

如(1) 状态 q0(开始状态) q1 q2 q3(终止状态) (2) 状态 q0(开始状态) q1 q2 q3(终止状态)

16、证明对于的FA M1=(Q1,∑1,δ1,q01,F1),FA M1=(Q2,∑2,δ2,q02,F2),存在FA M,

使得 L(M)= L(M1)∪L(M2) 证明:不妨设Q1 与Q2的交集为空

(1) 构造M=(Q1∪Q2∪{ q0},∑,δ, q0,F)其中:

1)∑=∑1∪∑2 F= F1∪F2 2) δ(q0,ε)={ q01 ,q02} 对于

q∈Q1,a∈∑1δ(q, a)=δ1(q,a)

0 { q1 q2 q3, } { q2} {,q2,q3} 空 1 { q0, q1,q2,q3} { q1,q2} { q0, q2,q3} { q0 } 0 { q0, q1,q2 q3} { q0, q1,q2,q3} { q0, q1,q2,q3} { q0, q1,q2,q3} 1 { q0, q1,q2,q3} { q1,q2,q3} {q1,q2,q3} { q0, q1,q2,q3} 对于 q∈Q2,a∈∑2 ,δ(q, a)=δ2(q,a)

(1) 证明:

1)首先证L(M1)∪L(M2)∈L(M)

设 x ∈L(M1)∪L(M2),从而有x ∈L(M1)或者x ∈L(M2),当x ∈L(M1)时 δ1(q01,x)∈F1

M的定义可得:

δ(q0,x)=δ(q0,εx)=δ(δ(q0,ε), x)=δ({q01 ,q02},x)=δ(q01 , x)∪δ(q02, x) =δ1(q01 , x) ∪δ(q01 , x)∈F1∪δ(q01 , x) 即x∈L(M) 同理可证当x ∈L(M2)时x∈L(M) 故L(M1)∪L(M2)∈L(M)

2) 再证明L(M)∈L(M1)∪L(M2)

设x∈L(M) 则δ(q0,x)∈F 由M的定义:

δ(q0,x)=δ(q0,εx)=δ(δ(q0,ε), x)=δ({q01 ,q02},x) =δ(q01 , x)∪δ(q02, x) 如果是δ(q01 , x) 因为Q1 与Q2的交集为空 而且δ(q0,x)∈F F= F1∪F2 则 δ(q01 , x)= δ1(q01 , x)∈F1 因此x∈L(M1)

如果是δ(q02 , x) 因为Q1 与Q2的交集为空 而且δ(q0,x)∈F F= F1∪F2 则 δ(q02 , x)= δ2(q02 , x)∈F1 因此x∈L(M2) 因此x∈L(M1)∪L(M2) L(M)∈L(M1)∪L(M2)得证 因此L(M)= L(M1)∪L(M2)

17 证明:对于任意的FAM1?(Q1,?1,?1,q01,F1),FAM2?(Q2,?2,?2,q02,F2),

存在FA M,使得L(M)?L(M1)L(M2).

证明:令 M ? (Q 1 ? Q 2 , ? , ? ,q ,{ f 2}) ,其中δ的定义为: 01 1) 对q∈Q1-{f1},a∈∑∪{ε} δ(q,a)=δ1(q,a);

2) 对q∈Q2-{f2},a∈∑∪{ε} δ(q,a)=δ2(q,a); 3) δ(f1,ε)={q02} 要证 L ( M ) ? L ( M 1 ) L ( M 2 ) ,

只需证明 L ( M 1 (M 2) ? L ( M ) , M 1 ) L ( M 2 ) ? L (M ) )LL(

1. 证明 L 1 ) L ( M 2 ) ? L (M )(M

121122

x?x1x2 使得

M1在处理x1的过程中,经过的状态全部都是Q1中的状态,所以在定义

M时,对?q?Q1,a??,?(q,x)??1(q,a)

故?(q01,x1)??1(q01,x2)?{f1}

M2在处理x2的过程中,经过的状态全部都是Q2中的状态,所以在定义

M时,对?q?Q1,a??,?(q,x)??2(q,a)

?(q02,x)??2(q01,x)?{f2}

下面证明x?L(M)设x?L(M)L(M),从而有x?L(M)并且x?L(M), ?(q01,x)??(q01,x1x2)??(?(q01,x1),x2)??(?1(q01,x1),x2)??(f1,x2)??(f1,?x2)????

2) 再证明

((f1,),x2)??(q02,x2)??2(q02,x2)?{f2}即得证x?L(M)L(M)?L(M1)L(M2)设x?L(M),即?(q01,x)?{f2}M是从q01启动的,由M的定义可知,M要达到状态f2,必须先到f1.由于除了对应状态转移函数式?(f1,?)?{q02}的移动外,不存在从f1出发的任何其他移动,而且该移动是f2的必经移动,所以,比存在x的前缀x1和后缀x2,使得x?x1x2,并且x1将M从状态q01引导到状态f1,x2将M从状态q02引导到状态f2.即?(q01,x)??(q01,x1x2)??(f1,x2)??(f1,?x2)??(q02,x2)?{f2}其中,?(q01,x1)?{f1},说明?1(q01,x1)?{f1};?(q02,x2)?{f2},说明?2(q02,x2)?{f2}

由于这表明x1?L(M1)x2?L(M2)从而x?x1x2?L(M1)L(M2) 故L(M)?L(M1)L(M2)综上所述,L(M)?L(M1)L(M2******************************************************************************* (吴丹 02282090)

18.证明:对于任意的FA M1=?Q1,?1,?1,q01,F1?,FA M2=?Q2,?2,?2,q02,F2?存在FA M,使得L?M?=L?M1?IL?M2?。证明:不妨将这些FA看成DFA 取M=?Q1?Q2,?1I?2,?,?q01,q02?,F?对于?a??1I?2,?q,p??Q,???q,p?,a?=???1?q,a?,?2?p,a???.?1?设:x?L?M?则?x?x1x2......xk其中xi?i??1,k????1I?2使得???q,p?,xi?????1?q,xi?,?2?p,xi????xi?L?M1?IL?M2??x?L?M1?IL?M2?从而可得L?M??L?M1?IL?M2??2?设:x?L?M1?IL?M2?则?x?x1x2......xk其中xi?i??1,k????1I有?1?q,xi?且?2?p,xi?从而使得?1?q,xi?=???q,p?,xi?;?2?p,xi?=???q,p?,xi??xi?L?M??x?L?M?从而可得L?M1?IL?M2??L?M?综合(1)(2)可得L?M?=L?M1?IL?M2?。又因为FA和DFA具有等价性,所以原命题得证。

?2

23.FA M的移动函数定义如下: δ(q0,3)={q0} δ(q0,1)={q1} δ(q1,0)={q2} δ(q1,1)={q3} δ(q2,0)={q2} δ(q3,1)={q3}

其中,q2,q3为终态.

(1) M是DFA吗为什么

不是,因为并不是所有的状态,在接收一个字母表中的字符时会有一个状态与之对应.

(2) 画出相应的DFA的状态转移图

q131q010q0,1,330,311,3

1q300q2(3) 给出你所画出的DFA的每个状态q的set(q):set(q)={x|xΣ*且δ(q0,x)=q} set(q0)={3*} set(q1)={ 3*1} set(q2)={ 3*100*} set(q3)={ 3*111*}

set(q)={( 3*0|3*13|3*100*(1|3)|3*111*(0|3)) 0*1*3*}

(4) 求正则方法G,使L(G)=L(M) q0→3 q0|1 q1 q1→0 q2|1 q3 q2→0|0 q2 q3→1|1 q3

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串(n0,m0) (5)((0+1)(0+1))* ((0+1)(0+1)(0+1))* 表示所有长度为3n+2m的0,1串(n0,m0) (6)00+11+(01+10)(00+11)*(10+01)表示的语言特征为长度为偶数n的串.当n=2时,

是00或11的串。n4时,是以01或10开头,中间的子串00或11成对出现,最后以10或01结尾的串

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4 ceshi