寻找给定语言的上下文无关文法
Finding a context-free grammar for the given language
我正在尝试为下面的语言 A 查找 CFG。
我已经为此花费了几个小时，但仍然找不到答案。我还想到这可能不是上下文无关语言，但实际上有一个 PDA 可以识别它。
如果有人能帮助我，我将不胜感激。
A={0^a 1^b 0^c 1^d| a+b < c+d, a,b,c,d>=1}
处理此类不等式的一个好方法是从等式的语法开始，然后添加一个或多个额外的符号。
这是一个更简单的示例，可能会让您入门。让我们看看语言
L = {0<sup>a</sup>1<sup>b</sup>0<sup>c</sup> | a+b < c, a,b,c ≥ 1}
我们从长度关系相等的语言开始：
L' = {0<sup>a</sup>1<sup>b</sup>0<sup>c'</sup> | a+b = c', a,b,c' ≥ 1}
现在，应该清楚了
L = {ω 0<sup>c"</sup>|ω ∈ 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，我们可以将0<sup>c'</sup>替换为0<sup>b</sup>0<sup>a</sup>，给我们：
L' = {0<sup>a</sup>1<sup>b</sup>0<sup>b</sup>0<sup>a</sup> | a,b ≥ 1}
这表明它是一种内部语言的组合，具有相同数量的 1 和 0，并被相同数量的前导和尾随 0 包围。换句话说：
L' ⇒ 0 M 0
L' ⇒ 0 L' 0
M ⇒ 1 0
M ⇒ 1 M 0
这让你成功了一半。祝你好运。
我正在尝试为下面的语言 A 查找 CFG。
我已经为此花费了几个小时，但仍然找不到答案。我还想到这可能不是上下文无关语言，但实际上有一个 PDA 可以识别它。
如果有人能帮助我，我将不胜感激。
A={0^a 1^b 0^c 1^d| a+b < c+d, a,b,c,d>=1}
处理此类不等式的一个好方法是从等式的语法开始，然后添加一个或多个额外的符号。
这是一个更简单的示例，可能会让您入门。让我们看看语言
L = {0<sup>a</sup>1<sup>b</sup>0<sup>c</sup> | a+b < c, a,b,c ≥ 1}
我们从长度关系相等的语言开始：
L' = {0<sup>a</sup>1<sup>b</sup>0<sup>c'</sup> | a+b = c', a,b,c' ≥ 1}
现在，应该清楚了
L = {ω 0<sup>c"</sup>|ω ∈ 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，我们可以将0<sup>c'</sup>替换为0<sup>b</sup>0<sup>a</sup>，给我们：
L' = {0<sup>a</sup>1<sup>b</sup>0<sup>b</sup>0<sup>a</sup> | a,b ≥ 1}
这表明它是一种内部语言的组合，具有相同数量的 1 和 0，并被相同数量的前导和尾随 0 包围。换句话说：
L' ⇒ 0 M 0
L' ⇒ 0 L' 0
M ⇒ 1 0
M ⇒ 1 M 0
这让你成功了一半。祝你好运。