A-A+

有文法G(S)： S→Aχ｜By A→y｜Ay B→χy 下面与文法G(S)表示相同语言的正

2022-08-12 20:23:37 问答库阅读 197 次

问题详情

有文法G(S)： S→Aχ｜By A→y｜Ay B→χy 下面与文法G(S)表示相同语言的正规式是_______。
A．y*χ｜χy｜y
B．y*χ｜χ｜χy
C．yyχ*χ｜χy｜y
D．yy*χ｜χy｜yy

请帮忙给出正确答案和分析，谢谢！

正确答案：D
L(G(S))＝{yiχ｜i≥1)∪{χy，yy}，所有句子的长度均大于1，所以选D。