automata - 为语言构建语法

Question

L = {a^i b^j c^k | not(i=j=k)}

提示：将 L 描述为其他语言的联合

我一直在尝试这样做一个星期，但我做不到。谁能帮我理解？

编辑 ：

说得对吗：

(i≠j or j≠k) 或者 (i≠j and j≠k and i≠k)

标签： automata

Answer 1

是否可以说：（i≠j 或 j≠k）或（i≠j 和 j≠k 和 i≠k）

这么说并没有错，但这比你需要说的要多。真的，你只需要说第一部分：

(i≠j 或 j≠k)

如果第一部分无论如何都不是真的，那么第二部分就不可能是真的。从这里，我们可以进一步分解：

i < j 或 i > j 或 j < k 或 j > k

这是四种非常基本的上下文无关语言的结合。如果你得到的语法 G1、G2、G3 和 G4 分别带有开始符号 S1、S2、S3 和 S4，你可以添加一个新的开始符号 S 和产生式 S -> S1 | S2 | S3 | S4 为他们的工会获取语法。