regular-language - 言語が規則的でないことを直接確認するにはどうすればよいですか

Question

L={a^nb^nc^n} が与えられた場合、生産規則を見ずに、この言語が規則的でないとどうすれば直接言えますか? 私はポンピング補題を使うことができますが、文法を見ただけでこれは正規のものではないと言っている人もいます。どのように可能ですか？

Answer 1

アルファベットには 3 文字あります。それらはすべて同じ変数 n に依存します。さて、それらが 2 つしかない場合、{a^nb^n} を想像してみてください。次のプロダクションでタスクを簡単に達成できます。

S -> ab | aSb

しかし、それらが 3 つあり、それらすべてを同じ変数にリンクする方法はありません。2 つの構文カテゴリを使用する必要がありますが、それを行っているため、それらはリンクされておらず、それぞれから異なる文字列を生成できます。それらをリンクする唯一の方法は、1 つの構文カテゴリのみを使用することであり、それは不可能です。

あなたはできません：

S -> abc | ASBC

実際、最終文字列に構文カテゴリを含めることはできないため、これは文字列ではありません。再度変換する必要があります。そして、そこから何ができるでしょうか？できるよ：

aabcbc

またはあなたが行うことができます：

aaSbcbc

最初のものは文字列であり、言語の一部ではありません。2 番目はまだ文字列ではありません。しかし、そこから許可された文字列を実行できないことは非常に簡単にわかります。