找出语言是否是上下文无关的
Find out if language is context-free or not
如果我有 {a^n b^n c^n | n > 0} \sum = {a,b,c}，我如何证明它是否是上下文无关语言？
我看过这里：，但对我来说意义不大。
我相信如果我这样做了
<S> ::= <A><B><C>|abc
<A> ::= a<A>
<B> ::= b<B>
<C> ::= c<C>
但我不确定。如有任何帮助，我们将不胜感激！
没有确定语言是否上下文无关的算法。找到一个上下文无关文法当然就足够了，但是没有算法可以做到这一点，所以它取决于技巧、直觉和运气。
语言 anbncn 众所周知不是上下文无关；你可以用泵引理证明这一点，因为它是一个常见的例子，你可以很容易地用 Google.
找到证明
你提出的文法并不能保证a、b、c的个数相等。它匹配由一些 a 后跟一些 b 后跟一些 c 组成的任何字符串。 （或者更好地说，如果你通过添加非递归基本案例使 A、B 和 C 产品有用，它就会这样做。）正是三向计数协议使语言不是上下文无关的。
如果我有 {a^n b^n c^n | n > 0} \sum = {a,b,c}，我如何证明它是否是上下文无关语言？
我看过这里：
我相信如果我这样做了
<S> ::= <A><B><C>|abc
<A> ::= a<A>
<B> ::= b<B>
<C> ::= c<C>
但我不确定。如有任何帮助，我们将不胜感激！
没有确定语言是否上下文无关的算法。找到一个上下文无关文法当然就足够了，但是没有算法可以做到这一点，所以它取决于技巧、直觉和运气。
语言 anbncn 众所周知不是上下文无关；你可以用泵引理证明这一点，因为它是一个常见的例子，你可以很容易地用 Google.
找到证明你提出的文法并不能保证a、b、c的个数相等。它匹配由一些 a 后跟一些 b 后跟一些 c 组成的任何字符串。 （或者更好地说，如果你通过添加非递归基本案例使 A、B 和 C 产品有用，它就会这样做。）正是三向计数协议使语言不是上下文无关的。