言語 (たとえば、L={a^nb^mc^s | 0<=n<=m<=s}) が、通常、コンテキストフリー、再帰的、再帰的に列挙可能か、またはそれらのどれでもないかどうかを判断する必要があります。
言語が正則 (機能する DFA または正規表現を見つける) か、文脈自由 (機能する PDA または文脈自由文法を見つける) かを判断する方法を知っています。再帰言語には常に停止するチューリング マシンがあり、再帰的に列挙可能な言語には停止しないチューリング マシンがあることを知っています。
問題は、言語が再帰的か、再帰的に列挙可能か、またはどちらでもないかを判断するための迅速な基準があるかということです。たとえば、言語が文脈自由であることを理解するために PDA を構築する必要はありません。1 つのスタックが必要であるという事実からはわかりません。問題に対する同様の迅速なアプローチはありますか (チューリング マシンを構築する手間が省けることを願っています)。
文脈自由言語の簡単な方法の 1 つは、比較回数を確認することです。
例では、 および を参照n<=mしてくださいm<=s。したがって、2 つの比較が含まれます。したがって、コンテキストフリーではないことを伝えるだけで、それを取り出すことができます。単一の比較が含まれる場合は、それを文脈自由言語と呼びます。
通常の言語も同様です。2 つの変数の間に関係があってはなりません。つまり、いかなる種類の比較があってはならないということです。たとえば、言語を考えてみましょう- 0^m+n 1^n 0^m. m+n = n+m(シンボルのプッシュとポップ) である 1 つの比較のみが行われていることを注意深く確認してください。つまり、コンテキスト フリーです。最初の 2 つと次の 2 つの比較がはっきりとわかります
。0^n+m 1^n+m 0^m
私はそれを理解するのに少し時間がかかりました。しかし、決定を下すには時間がかかります。本当にうまくいくと信じてください。これが通常の言語の最後の例です。a^n b^2m規則的 ( n と m の間に比較がないことを参照) であり、比較が{a^n b^m |n=2m}1 つしかないため (規則的ではない) コンテキストフリーです。
お役に立てれば
言語が再帰的か再帰的に列挙可能かを確認する構造的な方法はありません。実際、再帰言語を認識できるオートマトンには、オートマトンが受け入れる R 以外の RE 言語が少なくとも 1 つあるという、非常にクールな証明があります。これは、決定不能な問題の存在を示すために使用する対角化引数の変形です。
ある言語が RE にあるが R にはないことを証明する主な方法は、その言語が RE にあることを証明し (おそらくその言語に TM を定義することによって)、次に、R ではなく RE にある既知の問題をその問題に還元することです。たとえば、停止問題のインスタンスを問題のインスタンスに変換することで解決できることを示すことができれば、再帰的な解決策を持たないことがわかります。これを TM で追跡すると、その言語が RE であることを知っている言語。一緒にすると、R ではなく RE で言語ができます。