context-free-grammar - 此上下文无关语言的上下文无关语法

Question

以下语言的上下文无关语法？

L={a^m b^n a^k|Maximum(m,n) => k}  Σ={a,b}

Answer 1

实际上，该语言不是上下文无关的，因此不能由 CFG 表示。我们可以通过对上下文无关语言使用泵引理来看到这一点。

令 G 是一个乔姆斯基文法，使得 L(G) = L。令 j(通常称为 k)= 2^(n+1) 其中 n = G 中非终结符的数量。令 z = uvwxy 和 |vwx| <= j, |vx| > 0，根据抽水引理，对于所有 i >= 0，s_i = u(v^i)w(x^i)y 在 L 中。令 z = a^jb^j+1 a^j+1 .有几种情况选择 v 和 x 会产生矛盾。记住我们的语言是 {a^m b^n a^k | k = max(m,n)}。

案例1 v 和 x 都是 a* 形式:我们选择我们的字符串为 a^jb^j+1 a^j+1，所以抽上 a 将导致字符串 a^j+ib^j+1 a^ j+1+i 如果 v 和 x 分别来自第一个和第二个 a，则 a^j+2i b^j+1 a^j+1 如果 v 和 x 都在第一个 a 中，或者 a^jb^j +1 a^j+1+2i 如果它们都来自第二个。很明显，所有这些都是矛盾的，因为对于大 i，k 不等于 max(m,n)。

案例2 v 和 x 都是 b* 形式:我们只抽了 b，这意味着我们会得到 a^jb^j+1+2i a^j+1，它不被接受为 j+1 != j +1+2i。

案例3 v 的形式为 a*，x 的形式为 b*:因为 v 在 x 之前，所以 v 表示第一个 a 部分中的 a 的数量。但是因为我们要抽a's和b's，我们会得到a^j+i b^j+1+i a^j+1，所以k != max(m,n) 并且我们有矛盾。

案例4 v 是 b* 形式，x 是 a* 形式:这并不矛盾，因为我们以与 a^k 相同的速率增加最大值 (b^n)。

案例5 v 包含 a's 和 b's:如果我们把它抽起来，我们将得到 a^m 和 b^n 之间的子串 abab..ab 或 b^n 和 a^k 之间的子串 baba..ba，即不接受。

案例6 x 包含 a 和 b:类似于情况 6。

用 CFL 的抽水引理证明不规则是非常乏味的，但我希望这会有所帮助!