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

如（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结尾的串