时间戳

首页 > 解决方案 > 我如何获得这种语言的上下文无关语法？

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

问题描述

使用这种语言：

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

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

标签： context-free-grammarautomatapushdown-automaton

解决方案

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

  1. 始终根据联合和逻辑“或”拆分语言。在这种情况下，我们的语言L = {x^i, y^j, z^k : i != j ∨ j != k; i ≥ 0; j ≥ 0; k ≥ 0}在条件中有一个逻辑“或”，因此等价于两种语言与条件拆分的并集：L = L1 U L2whereL1 = {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 的每个开始非终结符。

  2. 将复杂条件重写为涉及简单条件的等效表达式，理想情况下，您已经知道如何编写 CFG。例如，i != j等价于i < j ∨ i > j。这允许我们将L1andL2从上面重写为L1 = {x^i, y^j, z^k : i < j ∨ i > j; i ≥ 0; j ≥ 0; k ≥ 0}and 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 L6where 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

要完成语法，只需使S' Ls CFG 的开始符号产生每个开始符号S3, S4, S5, S6：

S := S3 | S4 | S5 | S6

推荐阅读