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

EN

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

1. 总是根据联合和逻辑"or“拆分语言。在这种情况下，我们的语言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生产每个启动非终端，就可以形成一个用于两个CFLs的联合的CFG。

。

1. 将复杂条件重写为包含简单条件的等效表达式，理想情况下，您已经知道如何编写条件。例如，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}和L = L3 U L4 U L5 U L6

这些燃料的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

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

S := S3 | S4 | S5 | S6