我如何获得这种语言的上下文无关语法？

Question

使用这种语言：

L = {x^i, y^j, z^k : i != j ∨ j != k; i ≥ 0; j ≥ 0; k ≥ 0}, Σ = {x, y, z}

如何获得该语言的上下文无关文法？

Answer 1

有一些技巧可以用来解决这样的问题，这个问题至少受益于其中的几个：

始终根据并集和逻辑“或”拆分语言。在这种情况下，我们的语言 L = {x^i, y^j, z^k : i != j ∨ j != k; i ≥ 0; j ≥ 0; k ≥ 0} 在条件中有一个逻辑“或”，因此等效于两种语言的并集与条件拆分： L = L1 U L2 其中 L1 = {x^i, y^j, z^k : i != j; i ≥ 0; j ≥ 0; k ≥ 0} 和 L2 = {x^i, y^j, z^k : j != k; i ≥ 0; j ≥ 0; k ≥ 0}.两个 CFL 联合的 CFG 可以通过引入一个新的起始非终结符来形成，该起始非终结符为 CFL 的 CFG 生成每个起始非终结符。
将复杂条件重写为涉及简单条件的等效表达式，最好是您已经知道如何编写 CFG 的条件。例如，i != j 等同于 i < j ∨ i > j。这允许我们将上面的 L1 和 L2 重写为 L1 = {x^i, y^j, z^k : i < j ∨ i > j; i ≥ 0; j ≥ 0; k ≥ 0} 和 L2 = {x^i, y^j, z^k : j < k ∨ j > k; i ≥ 0; j ≥ 0; k ≥ 0}。请注意，我们现在可以使用上面的考虑重写 L1 = L3 U L4 和 L2 = L5 U L6，因此 L = L3 U L4 U L5 U L6 其中 L3 = {x^i, y^j, z^k : i < j; i ≥ 0; j ≥ 0; k ≥ 0}、L4 = {x^i, y^j, z^k : i > j; i ≥ 0; j ≥ 0; k ≥ 0}、L5 = {x^i, y^j, z^k : j < k; i ≥ 0; j ≥ 0; k ≥ 0} 和 L6 = {x^i, y^j, z^k : j > k; i ≥ 0; j ≥ 0; k ≥ 0}.

这些的 CFG 更容易生成：

S3 := S3 z | T3
T3 := x T3 y | T3 y | y

S4 := S4 z | T4
T4 := x T4 y | x T4 | x

S5 := x S5 | T5
T5 := y T5 z | S5 z | z

S6 := x S6 | T6
T6 := y T6 z | y S6 | y

要完成语法，只需让 L 的 CFG 的起始符号 S 产生每个起始符号 S3, S4, S5, S6:

S := S3 | S4 | S5 | S6

我如何获得这种语言的上下文无关语法？

How do I get the context free grammar of this language?

automata

context-free-grammar

pushdown-automaton