证明以下语言是上下文无关的：

这个问题是在一个样本考试中，我们的教授懒得打出解决方案，而我被卡住了很糟糕。在此先感谢您的帮助！证明以下语言是上下文无关的：

证明下列语言上下文{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}

来源

2012-04-05 Tarvaris Jackson

提示：DFA不能计数。 – cHao 2012-04-05 00:29:24

您可能会在Math.SE上获得更好的响应。 – 2012-04-05 00:53:46

@KendallFrey我会建议[CSTheory]（http://cstheory.stackexchange.com/）:) – 2012-07-16 19:06:19

{x是的元素{A，B，C} * |在X A的数目大于B的数目或c的在X}

这可以解释两种方式的数目大：

的a的数量大于（的b数量的加c数量的）
（的a数的比的b数大的）或（的a数的比的c数量更大的“ S）。

提示1：PDA可以工作如下。如果堆栈为空，并且在输入上看到一个a，则将一个a添加到堆栈。如果堆栈为空，并且在输入上看到b或c，请将b添加到堆栈。如果最上面的堆栈符号是b，并且您在输入上看到了a，请从堆栈中删除b。如果最上面的堆栈符号是b，并且您在输入上看到了b或c，请将另一个b添加到堆栈。如果最上面的堆栈符号是a，并且您在输入上看到了a，请将另一个a添加到堆栈。如果最上面的堆栈符号是a，并且您在输入上看到b或c，请从堆栈中删除a。现在简单地产生一个论点，即如果a的数目等于b和c的数目之和，则这样的PDA将具有（1）空的堆栈; （2）a如果它看到更多的a的比它看到b的或c的（组合）; （3）在堆栈顶部的b，如果它看到的数量比b或c（组合）的数量少a。

提示2：首先，构造一个PDA接受的a的，b的，而且比b小号c '其具有多个a s' 的任意字符串的，忽略任何c的（上面描述的PDA在提示1中可以很容易地修改为忽略c's）。然后，构建一个PDA，接受a的b和c的a的c的任意字符串，忽略任何b的（与您刚建立的类似）。最后，证明你试图证明上下文无关的语言是这些自动机接受的语言的结合;一个简单的论证就足够了。由于上下文无关的语言在联合下关闭，这就说明了这一说法，即您设置的用于证明上下文无关的语言的确是上下文无关的。

请随时要求进一步澄清。另外，请查看新网站，以获得如下问题：https://cs.stackexchange.com/。您可能会在该网站的未来问题上得到更好的答案。

来源

2012-04-05 13:47:57 Patrick87

-2

的任务是表明语言可以通过上下文无关文法产生。

一些提示：

A -> aabAc | B 
B -> B|epsilon

来源

2012-04-05 00:45:47 kasavbere

证明以下语言是上下文无关的：

回答

相关问题