主观题：h0023. 对下列语言构造相应的文法

分别对下列语言构造相应的文法：

① 可以以0开头的所有正偶数的集合;

② 不以0开头的所有奇数的集合；

③ 能被5整除的所有整数的集合；

④ 以a开头、b结尾的∑={a,b}上的任意符号串的集合；

⑤ {a^n#b^n | n≥0}∪{c^n#d^n |n≥0}；

⑥ {1^n0^m1^m0^n | m,n≥0}；

⑦ {w#w^r# | w∈{0,1}*,w^r表示将w中的符号按逆序排列所得的符号串}；







答案：分别对下列语言构造相应的文法：
① 可以以0开头的所有正偶数的集合;
参考答案：
e= (0 | 1 | 2 | …| 9)* (0 | 2 | 4 | 6 | 8)
G[S]:
S→(0 | 1 | 2 | …| 9) S | 0 | 2 | 4 | 6 | 8 -----------------------------------2分
② 不以0开头的所有奇数的集合；
e=(1|3|5|7|9) | (1|2|3|4|5|6|7|8|9)(0|1|2||3|4|5|6|7|8|9)* (1|3|5|7|9)
解：
S→BA|C
A→DA|C
B→1|2|3|4|5|6|7|8|9
C→1|3|5|7|9
D→0|B-----------------------------------2分
③ 能被5整除的所有整数的集合；
e=(0 | 1 | 2 | …| 9)* (0 | 5)
解：
S→0S | 1S | 2S | …| 9S | 0 | 5-----------------------------------2分
④ 以a开头、b结尾的∑={a,b}上的任意符号串的集合；
e=a(a|b)*b
解：
S→aA
A→aA | bA | b-----------------------------------2分
⑤ {a^n#b^n | n≥0}∪{c^n#d^n |n≥0}；
解：
S→A | B
A→aAb | #
B→cBd | #-----------------------------------2分
⑥ {1^n0^m1^m0^n | m,n≥0}；
解：
S→1S0 | A
A→0A1 | ε-----------------------------------2分
⑦ {w#w^r# | w∈{0,1}*,w^r表示将w中的符号按逆序排列所得的符号串}；
解：
S→A#
A→0A0 | 1A1 | #-----------------------------------2分