分类为规则的、上下文无关的或其他的

Question

有人能回答这些问题吗?请给我哑口无言，我没有完全理解这些想法。我对“终端机到底是什么？”“我们代表什么？”这样的事情感到困惑。

但对于真正的问题，请分类为规则，上下文无关，或其他。

( a) {a^nb^na^n} a's的∩#是偶数。

(a^nb^n)∪回文

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

请分类解释。

Answer 1

{a^nb^na^n} a's的∩#是偶数。

{a^n ^n^n}中的每个字符串都有2n a's，一个偶数，因此交集不再进一步限制语言。交集等于{a^n ^n^n}。这类似于一种对上下文敏感的规范语言a^n，b^n，c^n，我们可以用上下文无关语言的抽吸引理来证明语言不是上下文无关的。然后，请注意，如果a^n ^n^n是上下文无关的，那么您将期望(a+c)^n ^n (a+c)^n也是一样的，因为对于前者的任何PDA都可以只处理a和c并接受后者。然而，CFL和RL的交集必须是CFL，且(a+c)n b^n (a+c)^n相交aa_bb_cc*是a^n ^n^n (n > 0)，这不是上下文无关的，这是一个矛盾。另一个。

(a^nb^n)∪回文

假设这是正常的。然后，与所有奇数长度字符串的正则语言的交集将是规则的。上述联合中的所有奇数长度字符串都是奇数长度回文。奇数长的回文是不固定的，这是一个矛盾。现在，a^n ^n由CFG S := aSb aSb "“给出，回文是无上下文语言的典型例子，CFL的联合也是CFL，所以这是上下文自由的。

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

我们可以把它重写为a^n，a^m，b^m，a^2n。然后，我们看到这是无上下文的，因为CFG是S := Q；q := aQaa x“aRb；R := aRb x”。正则语言的抽吸引理可以证明它不是正则的。