言語の決定可能性
言語は呼ばれます Decidable または Recursive すべての入力文字列を受け入れて停止するチューリングマシンがある場合 w。決定可能なすべての言語はチューリングで受け入れられます。
決定問題 P 言語が決定可能である場合 L すべてのyesインスタンスの P 決定可能です。
決定可能な言語の場合、入力文字列ごとに、次の図に示すように、TMは受け入れ状態または拒否状態のいずれかで停止します。
例1
次の問題が決定可能かどうかを調べます-
数 'm'は素数ですか？
解決
素数= {2、3、5、7、11、13、…………..}
数を割る ‘m’ 「2」から始まる「2」から「√m」までのすべての数字。
これらの数値のいずれかが余りゼロを生成する場合、それは「拒否された状態」になり、そうでない場合は「受け入れられた状態」になります。したがって、ここで答えは「はい」または「いいえ」で作成できます。
Hence, it is a decidable problem.
例2
正規言語が与えられた L と文字列 w、どうすれば確認できますか w ∈ L？
解決
受け入れるDFAを取る L かどうかを確認します w 受け入れられます
さらに決定可能な問題は次のとおりです。
- DFAは空の言語を受け入れますか？
- Lである1 ∩L 2 =∅定期的なセットのためには？
Note −
言語の場合 L 決定可能であり、その補集合 L' 決定可能です
言語が決定可能である場合、その言語の列挙子があります。