GATE | GATE-CS-2006 |问题32

考虑上下文无关文法的下列语句

G = {S → SS, S → ab, S → ba, S → Ε}
I. G is ambiguous
II. G produces all strings with equal number of a’s and b’s
III. G can be accepted by a deterministic PDA.

下面哪个组合表达了关于G的所有真实陈述？ （A） 我只是 （B） 只有我和我 （C） 仅限II和III （D） 一、 二、三 答复: （B） 说明：

报表一： G是不明确的，因为如下图所示，字符串S=ababab[TRUE]可能有两个决策树

报表二： G生成a和b数量相等的所有字符串[假]

字符串“aabb”不能由G生成

报表三： G可被确定性PDA接受[真]

假设有一个PDA，如果堆栈顶部是$（堆栈最底部的字母表），它会推送，否则会弹出。如果当前字母和堆栈顶部相同，则弹出时会拒绝字符串。这个PDA可以导出G。

因此，正确答案应该是（B）I和III

参考： 语境无关语法和语境无关语言中的歧义

这个解决方案是由 维内特·珀斯瓦尼 . 这个问题的小测验