言語（例えば、L = {a^nb^mc^s | 0 < = n < = m < = s}）は、規則的、文脈自由、再帰的、再帰的に列挙可能かどうかを判断する必要があります。言語が再帰的か再帰的に列挙可能かどうかを判断するには？
言語が正規であるか（動作するDFAまたは正規表現を見つけるか）文脈自由（PDAまたは文脈自由文法が動作するかどうか）を判断する方法は知っています。再帰的言語には、常に停止するチューリングマシンがあり、再帰的に数え切れないほどの言語には、チューリングマシンが停止していない可能性があることがわかります。
質問には、言語が再帰的か再帰的に列挙可能かどうかを判断するための早い基準がありますか？たとえば、言語が文脈自由であることを理解するためにPDAを構築する必要はなく、1つのスタックが必要であるという事実ではわかりません。問題への同様の速いアプローチがあります（うまくいけば、チューリングマシンを構築するのに苦労しないでしょう）？
言語が再帰的か、再帰的に列挙可能かどうかを確認する構造的な方法はありません。実際には、再帰的言語を認識できる任意のオートマトンに対して、オートマトンも受け入れるRにない少なくとも1つのRE言語が存在するという、本当にクールな証拠があります。決めることができない問題の存在を示すために使用する対角化論の変種です。
言語がREではなくRであることを証明する主な方法は、言語がREにあることを証明することです（恐らくTMを定義することによって）。問題。たとえば、停止問題のインスタンスが問題のインスタンスに変換することによって解決できることを示すことができれば、それは再帰的解決策を持つことができないことを知っています。言語はREになっています。一緒に、あなたはREではなくRで言語を持っています。
文脈自由言語の1つのクイックメソッドはちょうど比較の数を見ています。
この例では、n<=mとm<=sを参照してください。したがって、2つの比較が関係しています。だから、文脈自由ではないということだけを伝えることができます。単一の比較が関与している場合は、それをコンテキストフリーの言語として呼び出します。
普通の言語と同じです。 2つの変数の間には何の関係もないはずです。つまり、何の比較もあってはならないと言うことです。例については、言語-0^m+n 1^n 0^mを考慮する。慎重に、ただ一つの比較がm+n = n+m（シンボルのプッシュとポップ）であることを確認してください。
0^n+m 1^n+m 0^mは、最初の2と次の2つの比較を明確に見てください。
私はそれを理解するのに時間がかかりました。しかし、決定を下すにはいくらかの時間がかかります。本当にうまくいくと私は信じています。ここでは、通常の言語の最後の例があります。 a^n b^2mは（nとmの間には比較は存在しない参照してください）定期的であり、それは（規則的ではない）だけ1つの比較
希望これは確か私が望んでいた答えではありません
@ saurabh srivastav L = {a^n b^m | n、m> = 1}は、このCFLですか？ –
@aparajitarai私は、Lは普通の言語だから、aの数とbの数の関係は本当に気にしないので、言語の各文字列はいくつかの非（これは定義されていませんが、nは何であるべきですか？）bの空ではないシーケンス（mの長さの上限は再び制約されません）の前に、この言語の表現。私が間違っている場合は私を修正してください。私は私の大学で理論計算科学のコースを取っているだけです。 – jcxz
を助けを持っているよう
{a^n b^m |n=2m}は文脈自由です私が最初に書いた例を解決しなければならない場合は、どのように進行しますか（文脈自由ではないことを知っていますか？） – Jacob@ Jacob-Are文脈自由ではないと確信していますか？ – templatetypedef
確かに、ええ..ポンプ補助定理はそれを排除しなければなりませんし、うまくいく文法も見つけられません。 – Jacob