文法G[S]:S→xSx|y所描述的语言是______(n≥0)。A.(xyx)nB.xyxnC.xynxD.xnyxn

Question

文法G[S]：S→xSx|y所描述的语言是______(n≥0)。

A．(xyx)n

B．xyxn

C．xynx

D．xnyxn

Answer 1

正确答案：D
解析：正规文法到正规式的转换规则如下：
 
  在本题中，推导过程如下：
  S-＞xSx－＞xyx－＞x²Sx²-＞x²yx²-＞
  x³Sx³-＞x³yx³-＞...-＞xⁿSxⁿ-＞xⁿyxⁿ
  得出生成式的规律是：两个x串中间只有一个y，同时两边的x串等长。