context-free-grammar - Automata：以下语言的 CFG

Question

请看以下语言：

(a, b, c)* − {anbncn|n≥0}

我的问题是：我如何为它写一个上下文无关语法？

一般来说，当某些东西被排除在外（即有“-”号）时，我该如何编写语法？

Answer 1

没有算法可以确定一种语言是否是上下文无关的。因此，您提出的问题没有通用的解决方案也就不足为奇了。

上下文无关语言不会在互补、集差或交集下封闭。（但它们在串联、集合并集和 Kleene 星号下是封闭的。）无论如何

{anbncn|n≥0}

不是上下文无关的语言，但它的补充（如您的问题）是上下文无关的。这一事实的证明（通过为补语构建上下文无关文法）是补语下 CFG 不闭合的标准示例。

概括地说，您的语言 L 可以由以下组合组成：

• {a,b,c}字母表中字母不按顺序排列的所有字符串。换句话说，所有包含子字符串的字符串ba，cb或ca。

• {aibjck|i,j,k≥0∧i≠j}

• {aibjck|i,j,k≥0∧j≠k}

Answer 2

(a, b, c)* − {a^nb^nc^n|n≥0}

这表示您可以选择 a、b 或 c 中的任何一个，并重复其中任何一个，例如 abccbaabaab 或 abca 或 bccc

对于 a*，您可以使用A->aA |e或A->AA | a | e。

使用该规则，您可以执行以下操作：

S -> A | B | C A->aA |e | AS B->bB |e | BS C->cC |e | CS

如果整个事物上有一个 Kleene 星，则可以在 A、B 和 C 中的每一个中包含 S (....)*，并允许您回到开始并添加另一个符号。

我不知道如何制作一个排除符号的语法，但从逻辑上讲，如果-不是可用的终端符号，你已经排除了它。