context-free-language - 找出语言是否与上下文无关

Question

如果我有{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>

但我不确定。任何帮助，将不胜感激！

Answer 1

没有用于确定语言是否是上下文无关的算法。当然，找到一个上下文无关的语法就足够了，但是没有算法可以做到这一点，所以它取决于技能、直觉和运气。

众所周知，语言 a ⁿ b ⁿ c ⁿ不是上下文无关的；您可以使用抽水引理证明这一点，并且由于它是一个常见示例，因此您可以使用 Google 很容易地找到一个证明。

您提出的语法不保证 a、b 和 c 的数量相等。它匹配任何由一些 a 和一些 b 和一些 c 组成的字符串。（或者更好地说，如果您通过添加非递归基本案例使 A、B 和 C 产生式变得有用，它会做到这一点。）正是三向计数协议使语言不是上下文无关的。