GATE | GATE IT 2006 |问题34

在下面的上下文无关语法中，S是起始符号，a和b是终端，ϵ表示空字符串。

s→ 尽快|ϵ A.→ 巴|ϵ

语法生成语言 （A） （（a+b）*b）* （B） {a ^M B ^N |m≤ n} （C） {a ^M B ^N |m=n} （D） a*b* 答复: （B） 说明： 从A： （（a+b）*b）* 它接受aa字符串，但给定语法则不接受。 给定语法所接受的最简单字符串是abb，因此选项C不为true，选项D也为false。 这个问题的小测验