查找给定语言的上下文无关语法

Question

我正在尝试为以下语言A找到CFG。我已经花了几个小时，但是仍然找不到答案。我还想到了这可能不是上下文无关的语言，但实际上是可以识别它的PDA。如果有人可以帮助我，我将非常感激。

                          A={0^a 1^b 0^c 1^d| a+b < c+d, a,b,c,d>=1}

Answer 1

处理这样的不平等现象的一种好方法是从等式的语法开始，然后添加一个或多个额外的符号。

这是一个简单的示例，可能会让您入门。让我们看看语言

L = {0a1b0c | a+b < c, a,b,c ≥ 1}

我们从长度之间的关系相等的语言开始：

L' = {0a1b0c' | a+b = c', a,b,c' ≥ 1}

现在，应该清楚

L = {ω 0c"|ω ∈ L', c" ≥ 1}

换句话说，L由L'中的字符串组成，后跟一个或多个零。原始的c已拆分为c' + c"。

给定L，很容易为L'编写语法：

L ⇒ L' 0
L ⇒ L 0

或者，如果您愿意：

L ⇒ L' Z
Z ⇒ 0  
Z ⇒ Z 0  

所以现在我们只需要研究L'。由于我们知道c' = a + b，因此可以将0c'替换为0b0a，从而得到：

L' = {0a1b0b0a | a,b ≥ 1}

这表明是​​一种内部语言的组合，该内部语言具有相同的1和0，并被相同数量的前导和尾随0包围。换句话说：

L' ⇒ 0 M 0
L' ⇒ 0 L' 0 
M ⇒ 1 0
M ⇒ 1 M 0

这可以使您顺利完成一半。祝原问题顺利。