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

状态说明 状态 0 输入字符 1 {q0,q2} 2 {q0,q2} {q2} 开始状态 q0 q1 q2 q3 {q0,q1} {q3,q0} ? {q3,q2} {q3,q1} {q3 } {q2,q1} { q0} 终止状态 解答：

状态说明 状态 0 输入字符 1 [q0,q2] [q0,q2] [q0,q1,q2,q3] [q0,q1,q2,q3] [q0, q2,q3] [q0,q1,q2,q3] 2 [q0,q2] [q0,q2] [q0,q1,q2] [q0,q1,q2] [q0,q2] [q0,q1, q2] 开始状态 q0 [q0,q1] [q0,q2] [q0,q1,q2] [q0,q1,q3] [q0,q2,q3] [q0,q1] [q0,q1,q3] [q0,q1] [q0,q1,q3] [q0,q1,q2,q3] [q0,q1,q2,q3] 终止状态 终止状态 终止状态 [q0,q1,q2,q3] [q0,q1,q2,q3] [q0,q1,q2,q3] [q0,q1, q2] q0[q0,q1]001,201,22[q0,q1,q3][q0,q2,q3]12[q0,q1,q2]210,1[q0,q1,q2,q3]2

00,1[q0,q2]

参 考 题 目

1、设??{a,b,c},，构造下列语言的文法。 (1) L1?{anbn|n?0}。

解答：G1?({S},{a,b},{S?aSb|?},S)。 (2) L2?{anbm|n,m?1}。

解答：G2?({S,A,B},{a,b},{S?A|B,A?aA|a,B?bB|b},S)。 (3) L3?{anbnan|n?1}。

解答：G3?({S,A,B},{a,b},P3,S) P3: S →aAB|aSAB BA→AB aB→ab bB→bb bA→ba aA→aa

(4) L4?{anbmak|n,m,k?1}。

解答：G4?({S,A},{a,b},{S?ABA,A?aA|a,B?bB|b},S)。

? (5) L5?{awa|a??,w??}。

解答：G5?({S,W},{a,b,c},{S?aWa,W?aW|bW|cW|a|b|c},S)。 (6) L6?{xwxT|x,w??}。

? 解答：G6?({S,W},{a,b,c},P6,S) P6:S?aWa|bWb|cWc W?aW|bW|cW|a|b|c。

T? (7) L7?{w|w?w,w??}。

解答：G7?{{S,W},{a,b,c},{S?aWa|bWb|cWc|a|b|c},S}。

(8) L8?{xxTw|x,w???}。

解答：G8?({S,W,X},{a,b,c},P8,S) P8:S?XW

X?aXa|bXb|cXc|a|b|c W?aW|bW|cW|a|b|c。

2、给定RG：G1?(V1,T1,P1,S1)，G2?(V2,T2,P2,S2)，试分别构造满足下列要求的RG G，并证明你的结论。

(1)L(G)?L(G1)L(G2)

解：不妨假设V1?V2??，并且S?V1?V2，令G???S??V1?V2，T1?T2，P1?P2?P3，S?其中，P3?S??S2??T1且S1????S??S1?????S???????证明：（1）设x?L?G?，则S?x*若x??，因为??L?G1?，??L?G2?，所以??L?G1?L?G2? 成立若x??，由产生式S??S2，不妨设x?x1x2，其中x1?T1，x1?L?G1??则S2?x2，因为G的产生式包括P2，所以x2?L?G2?，可知x?x1x2?L?G1?L?G2?*所以 L?G??L?G1?L?G2?（1）设x?L?G1?L?G2?，不妨设x?x1x2，其中x1?T1，S1?x1，x2?T2，S2?x2****x1??时，由P3中S??S2??T1且S1??，则S?所以 x1x2?L?G?，L?G1?L?G2??L?G?x1??时，由P3中?S??S1??? S?x2*?????x1S2??x1x2x2??时，由S??，得S?x2 所以x2?L?G?*L?G1?L?G2??L?G?综上，L?G??L?G1?L?G2?

(2)L(G)?L(G1)?L(G2)

解：不妨假设V1?V2??，并且S?V1?V2，令G???S??V1?V2，T1?T2，P1?P2?P3，S?其中，P3??S??S1??或S2???证明：（1）设x?L?G1??L?G2? 不妨设x?L?G1? 那么可知S1?x*

由G构造方法可知，S?x 且x?L?G? 即L?G1??L?G2??L?G?*（2）设x?L?G? 则S?x，由P3知，S1?x或S2?x***不妨设S1?x 则 x?L?G1? ， L?G1??L?G?*同理 L?G2??L?G? 则 L?G1??L?G2??L?G?所以 L?G??L?G1??L?G2?(3)L(G)?L(G1)?a,b?L(G2),其中a，b是两个不同的终极符号

解：不妨假设V1?V2??，并且S?V1?V2，令G???S??V1?V2，T1?T2，P1?P2?P3，S?其中，P3?S??aS2?bS2其中??T1且S1????S??S1???**??证明：（1）设x?L?G? 则S?x 由产生式S??aS2，不妨设x??1a?2 *则?1?T1，S2??2 则?1?L?G1?，?2?L?G2?**所以x??1a?2?L(G1)?a,b?L(G2) 同理?1b?2?L(G1)?a,b?L(G2)可得L(G)?L(G1)?a,b?L(G2) （2）设x?L(G1)?a,b?L(G2) 不妨设x??1a?2 其中?1?L(G1)，?2?L(G2) 即S1??1，S2??2 由P3中产生式 S??1aS2??1a?2所以L(G1)?a,b?L(G2) ?L?G?综上可得，L(G)?L(G1)?a,b?L(G2)(4)L(G)?L(G1)

****

解：

P={S→α|S1→α∈P1}∪{S→ε}∪{S→αS|S1→α∈P1} 证明略。

(5)L(G)?L(G1)

?解：

P={S→α|S1→α∈P1}∪{S→αS|S1→α∈P1} 证明略。

3、设文法G有如下产生式： S→aB│bA

A→a│aS│bAA

B→b│bS│aBB

证明L(G)＝{ω│ω中含有相同个数的a和b，且ω非空}。

证：观察发现A的产生式A→bAA中的bA可以用S来代替，同样B的产生式B→aBB中的

aB也可以用S代替。这样原来的文法可以化为如下的形式： S→aB│bA

A→a│aS│SA B→b│bS│SB

进一步地，可以把产生式A→aS中的S代换，把文法化为如下的形式： S→aB│bA

A→a│aaB│abA│SA B→b│baB│bbA│SB

7．设DFA M=(Q,?,?,q0,F)，证明：对于?x,y??,q?Q,?(q,xy)??(?(q,x),y) 注：采用归纳证明的思路

证明： (周期律 02282067) 首先对y归纳，对任意x来说，|y| = 0时，即y=?

根据DFA定义?(q,?)?q,?(q,xy)??(q,x)??(?(q,x),?)??(?(q,x),y),故原式成立。

当|y| = n时，假设原式成立，故当|y|= n+1时， 不妨设y = wa, |w| = n, |a| = 1

根据DFA定义?(q,xa)??(?(q,x),a),a??，故

*?(q,xy)??(q,xwa)??(?(q,xw),a)??(?(?(q,x),w),a)??(?(q,x),wa)??(?(q,x),y)原式成立，

同理可证，对任意的y来说，结论也是成立的。

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库形式语言与自动机理论试题(2)在线全文阅读。