单选题
文法G[S]：S→xSx｜y所描述的语言是______ (n≥0)。
A、
(xux)
n
B、
xyx
n
C、
xy
n
x
D、
x
n
yx
n
【正确答案】
D
【答案解析】
[分析] 根据文法所描述的推导规则，推导过程是这样的：
S→xSx→x
2
Sx
2
→x
3
Sx
3
→...→x
n
Sx
n
→x
n
yx
n
同时又有
xSx→xyx；x
2
Sx
2
→x
2
yx
2
，...
因此从两个式子得出规律：字符串中间只有一个y，两边有相同数目的x。
提交答案
关闭