状态说明 状态 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来说，结论也是成立的。