0

这个问题是在一个样本考试中，我们的教授懒得输入答案，我被困得很糟糕。在此先感谢您的帮助！

证明以下语言是上下文无关的{x is an element of {a,b,c}* | the number of a's in x is greater than the number of b's or the number of c's in x}

4

2 回答 2

1

{x 是 {a,b,c}* 的一个元素 | x 中 a 的数量大于 b 的数量或 x 中 c 的数量}

这可以解释为两种方式：

  1. 的个数a大于（的个数b加上 的个数c）
  2. （a'的数量大于b'的数量）或（a'的数量大于c'的数量）。

提示 1：PDA 可以按如下方式工作。如果堆栈为空并且您a在输入中看到一个，则将一个添加a到堆栈中。如果堆栈为空并且您在输入中看到 ab或 a ，则将 a 添加到堆栈中。如果最顶部的堆栈符号是 a并且您在输入中看到 an ，则从堆栈中删除 a 。如果最顶部的堆栈符号是 a并且您在输入中看到 a或 a ，则将另一个添加到堆栈中。如果最顶部的堆栈符号是 an并且您在输入中看到 an ，则将另一个添加到堆栈中。如果最顶部的堆栈符号是 an并且您在输入中看到 a或 a ，请删除cbbabbbcbaaaabca从堆栈中。现在简单地产生一个参数，这样一个 PDA 将有 (1) 如果 's 的数量a等于b's 和c's 的数量之和，则该 PDA 将具有一个空堆栈；(2)如果它看到的 's 比它看到的's 或's (组合)a多，则在堆栈顶部；(3) a在堆栈顶部，如果它看到的's 少于它看到的's 或's（组合）。abcbabc

提示 2：首先，构造一个 PDA 接受a's、b's 和c's 的任何字符串，其中a's 比b's 多，忽略任何c's（上面在提示 1 中描述的 PDA 可以很容易地修改为忽略c的）。然后，构造一个 PDA 接受任何字符串a' bs 和c's，其中a's 比c's 多，忽略任何b's（类似于您刚刚构建的那个）。最后，证明你试图证明上下文无关的语言是这些自动机接受的语言的联合；一个简单的论据就足够了。由于无上下文语言在联合下是封闭的，这证明了这一主张，即您开始证明无上下文的语言是，

请随时要求进一步澄清。此外，请查看新站点以了解以下问题：https ://cs.stackexchange.com/ 。您可能会在该站点上收到关于未来问题的更好答案。

于 2012-04-05T13:47:57.323 回答
-2

任务是证明语言可以由上下文无关文法生成。

一些提示：

A -> aabAc | B
B -> B|epsilon
于 2012-04-05T00:45:47.747 回答