分類爲常規，上下文無關，或其他

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 | 「」。通過正則語言的抽象引理可以證明它不是常規的。