context-free-grammar - 分类为常规、上下文无关或其他

Question

有人可以回答这些问题并为我简化，我没有完全掌握这些想法。我对诸如“终端到底是什么？”“w 代表什么？”之类的东西总体上感到困惑。

但至于真正的问题，请归类为常规、无上下文或其他。

a) {a^nb^na^n} ∩ # 个 a 是偶数。
b)(a^nb^n) ∪ 回文
c)a^n+mb^ma^2n

请分类说明。

Answer 1

{a^nb^na^n} ∩ # 个 a 是偶数。

{a^nb^na^n} 中的每个字符串都有 2n 个 a，一个偶数，因此交集不会进一步限制语言。交集等于 {a^nb^na^n}。这类似于一种规范的上下文相关语言 a^nb^nc^n。我们可以使用上下文无关语言的泵引理来证明语言不是上下文无关的。然后，请注意，如果 a^nb^na^n 是上下文无关的，您会期望 (a+c)^nb^n (a+c)^n 也是如此，因为前者的任何 PDA 都可以处理a 和 c 相同并接受后者。但是，CFL 和 RL 的交集必须是 CFL 并且 (a+c)^nb^n (a+c)^n intersect aa bb cc* 是 a^nb^nc^n (n > 0)，这不是上下文无关的，是矛盾的。其他。

(a^nb^n) ∪ 回文

假设这是正常的。那么所有奇数长度的字符串与正则语言的交集将是正则的。上述联合中的所有奇数长度字符串都是奇数长度回文。奇数回文不规则，矛盾。现在，a^nb^n 由 CFG S := aSb | 给出。"" 和回文是上下文无关语言的典型例子，CFL 的并集也是 CFL，所以这是 CONTEXT FREE。

a^(n+m) b^(m) a^(2n)

我们可以将其重写为 a^na^mb^ma^2n。然后我们看到这是 CONTEXT FREE，因为 CFG 是 S := Q; 问：= aQaa | "" | R; R := aRb | “”。正则语言的抽引引理可以证明它不是正则的。