theory - 上下文自由泵引理

Question

以下语言上下文是免费的吗？

L = {a^i b^k c^r d^s | i+s = k+r, i,k,r,s >= 0}

我试图想出一个上下文无关的语法来生成它，但我做不到，所以我假设它不是上下文无关的。至于我的反证法：

假设 L 是上下文无关的，

令 p 是由泵引理给出的常数，

选择字符串 S = a^pb^pc^pd^p 其中 S = uvwxy

作为 |vwx| <= p，那么 vwx 最多可以包含两个不同的符号：

情况 a) vwx 仅包含单一类型的符号，因此 uv^2wx^2y 将导致 i+s != k+r

案例 b) vwx 包含两种类型的符号：

i) vwx 由 b 和 c 组成，因此 uv^2wx^2y 将导致 i+s != k+r

现在我的问题是，如果 vwx 由 a's 和 b's，或 c's 和 d's 组成，那么泵送它们不会破坏语言，因为 i 和 k 或 s 和 r 可能会一致增加，导致 i+s == k +r。

我做错了什么还是这是一种上下文无关的语言？

score 1 · Accepted Answer

我也无法想出一个 CFG 来在我的脑海中生成那种特定的语言，但我们知道，如果某个下推自动机识别出一种语言，那么它就是上下文无关的。

设计这样的PDA 不会太难。一些帮助您入门的想法：我们知道 i+s=k+r。等效地，ik-r+s = 0（我按那个顺序写它，因为这是它们出现的顺序）。问题的关键是决定如果 (k+r)>i 时如何处理堆栈。

如果您不熟悉 PDA 或无法使用它们来回答问题，至少您现在知道它是无上下文的。

祝你好运！

score 0 · Accepted Answer

这是一个接受这种语言的语法：

A -> aAd
A -> B
A -> C
B -> aBc
B -> D
C -> bCd
C -> D
D -> bDc
D -> ε

2 回答 2