有限自动机答案第二章答案不全.doc

*******************************************************************************
1. 设L = { 0n | n ≥ 1 },试构造满足要求的文法G.
(1) G是RG.
(2) G是CFG, 但不是RG.
(3) G是CSG, 但不是CFG.
(4) G是短语结构文法,但不是CSG.
解答：
1：S→0|0S
2：S→0|0S|SS
3：S→0|0S|AS
AS→SA
AS→0A
0A→S0
0AS→00
4：S→0|0S|AS
AS→SA|ABB
ABB→AS
AB→A|ε
*******************************************************************************
2．设∑={0,1},请给出∑上的下列语言的文法
(1)所有以0开头的串
S→0A|0
A→0|1||0A|1A
(2)所有以0开头以1结尾的串
S→0A
A→1|0A|1A
(3)所有以11开头以11结尾的串
S→11A|11
A→11|0A|1A
(4)所有最多有一对连续的0或者最多有一对连续的1
1：x中既没有成对的0，也没有成对的1
2：x有一对连续的0
3： x有一对连续的1
4：x中既有一对连续的0，也有一对连续的1
S→A|B|C|D
A→ε|A’|A”
A’ →0|01|01A’
A” →1|10|10A”

B→B’00B”
B’ →1|01|1B’|01B’
B” →1|10|1B”10B”

C→C’11C”
C’ →0|10|0C’|10C’
C” →0|01|0C”|01C”

D→E00F11H|P11G00K
E→1|1E’|E’
E’ →01E’|E’
F→ε|10|10F // F 以1开头，以0结尾；不含连续0和连续1
H→0|H’0|H’
H’ →01|01H’
P→0|0P’|P’
P’ →10P’|10
G→ε|01|01G // G 以0开头，以1结尾；不含连续0和连续1
K→1|K’1|K’
K’ →10|10K’
(5) 所有最多有一对连续的0而且最多有一对连续的1
1：x中既没有成对的0，也没有成对的1
2：x只有一对连续的0，没有连续的1
3：y只有一对连续的1，没有连续的0
4：x中既有一对连续的0，也有一对连续的1
S→A|B|C|D
A→ε|A’|A”
A’ →0|01|01A’
A” →1|10|10A”

B→B’00B”’
B’ →ε|1|01|01B’’|1 B’’ // B’是不含连续0，也不含连续1的串
B’’ →01|01 B’’
B”’ →ε|1|10|10B”” // B””是不含连续0，也不含连续1的串
B”” →10|10 B””

C→C’11C”’ // C’是不含连续1，也不含连续0的串
C’ →ε|0|10|0C”|10C”
C” →10|10 C”
C”’ →ε|0|01|01C”” // C””是不含连续1，也不含连续0的串
C”” →01|01 C””

D→E00F11H|P11G00K
E→1|1E’|E’
E’ →01E’|E’
F→ε|10|10F // F 以1开头，以0结尾；不含连续0和连续1
H→0|H’0|H’
H’ →01|01H’
P→0|0P’|P’
P’ →10P’|10
G→ε|01|01G // G 以0开头，以1结尾；不含连续0和连续1
K→1|K’1|K’
K’ →10|10K’
(6)所有长度为偶数的串
S→01|10|00|11|01S|10S|00S|11S
(7)所有包含子串01011的串
S→X01011Y
X→ε|0X|1X
Y→ε|0Y|1Y
(8)所有含有3个连续0的串
S→X000Y
X→ε|0X|1X
Y→ε|0Y|1Y
*******************************************************************************
3 设，构造下列语言的文法。
(1) 。
解答：。
(2) 。
解答：。
(3) 。
解答：
S →aAB|aSAB
BA→AB
aB→ab
bB→bb
bA→ba
aA→aa

(4) 。
解答：。
(5) 。
解答：。
(6) 。
解答：

。
(7) 。
解答：。
(8) 。
解答：

。
*******************************************************************************