context-free-grammar - 这是一种非上下文无关的语言吗？我可以用自动机来描述它吗？

Question

我很难知道这种语言是否与上下文无关。

The Language is: "L={a^n*a^z*b^n*b^z*c^n*c^k|n≥0, z≥0, k≥0}".

在我看来，这种语言不是上下文/自由的，因为我无法用自动机描述 z=k=0 的情况，在这种情况下我会：L = (a^n*b^n*c^n)这显然不是上下文无关的语言。但我无法使用 Pumping Lemma（在起始语言上）并确保我的想法。

标签： context-free-grammarautomatafinite-automatacontext-free-language

Answer 1

n在该描述中没有任何目的；任何与标准匹配的字符串也与标准匹配。（只需设置。）并且该语言可以用上下文无关语法来描述：apbpcqp, q ≥ 0p = n + z; q = n + k

S → A C
A → a A b | ε
C → C c | ε

这里的一个要点是算术表达式中的隐式结构不会自动成为该算术表达式所描述事物的一部分。（或者，换句话说，在你连接两个字符串之后，你不再看到它们之间的边界。）另一个可能更实际的收获是，大多数关于形式语言的考试问题都很复杂，以使答案不明显，所以从某种意义上说，它们几乎都是技巧问题。