分类为常规，上下文无关，或其他

Question

有人可以回答这些问题，并请给我愚蠢的，我没有完全掌握的想法。我总是困惑于诸如“终端究竟是什么？”“W代表什么？”

但是至于真正的问题，请将它们分类为常规，上下文无关或其他。

a）{a^nb^na^n}∩a的a是偶数。
B）（A^NB^N）∪回文
c）一种^ N + M B ^米^ 2n个

请分类和解释。

Answer 1

{a^nb^na^n}∩a的数目是偶数。

{a^n b^n a^n}中的每个字符串都有2n个a，偶数，所以交集不会进一步限制语言。该交点等于{a^n b^n a^n}。这与典型的上下文敏感语言之一类似。我们可以使用上下文无关语言的抽象引理来显示语言不是上下文无关的。然后，请注意，如果一个上下文无关联，您会期望（a + c）^ nb^n（a + c）^ n也是如此，因为前者的任何PDA都可以处理a和c相同并接受后者。然而，CFL和RL的交点必须是CFL并且（a + c）^ nb^n（a + c）^ n相交于cc *并且cc *是a nb^nc^n（n> 0 ），这是不上下文的矛盾。其他。

（一个^ NB^N）∪回文

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

一个^（N + M）b ^（M）A ^（2N）

我们可以重写此作为^ N A^M B ^米^ 2n个。然后我们看到这是无上下文的，因为CFG是S：= Q;问：= aQaa | “” R等R：= aRb | “”。通过正则语言的抽象引理可以证明它不是常规的。