は、通常、文脈自由、またはその他と分類されます

Question

誰かがこれらの質問に答えることができ、私のためにそれを黙ってください、私は完全にアイデアを把握していません。私は、「ターミナルは正確に何か？」「wは何を意味するのか？

ここでの本当の質問は、通常、文脈自由、またはその他のものとして分類してください。

a）{a^nb^na^n}∩は偶数です。
B）（^ NB^N）∪回文
C）A^N + m個のB^m個のA^2N

分類して説明してください。

Answer 1

{a^nb^na^n}∩は偶数です。

{a^n b^n a^n}のすべての文字列は2n aの偶数であるため、交差点は言語をそれ以上制限しません。交点は{a^n b^n a^n}に等しい。これは、標準的な文脈依存言語の1つであるa^n b^n c^nに似ています。文脈自由言語のポンピング補題を使用して文脈自由でないことを示すことができる。それで、もし^ nb^na^nが文脈自由であれば、前者のPDAはちょうどそれを扱うことができるので、あなたは（a + c）^ nb^n（a + c）^ nもそうであると思うでしょうaとcは同じで、後者を受け入れます。ただし、CFLとRLの交点はCFLでなければならず、（a + c）^ nb^n（a + c）^ nは交差するaa bb 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^m個のA^2Nとしてこれを書き換えることができます。 CFGはS：= Qであるため、これはCONTEXT FREEです。 Q：= aQaa | "" | R; R：= aRb | ""定期的な言語のポンピング補題では、規則的でないことが示されます。