問題タブ [turing-machines]

言語 (たとえば、L={a^nb^mc^s | 0<=n<=m<=s}) が、通常、コンテキストフリー、再帰的、再帰的に列挙可能か、またはそれらのどれでもないかどうかを判断する必要があります。

言語が正則 (機能する DFA または正規表現を見つける) か、文脈自由 (機能する PDA または文脈自由文法を見つける) かを判断する方法を知っています。再帰言語には常に停止するチューリング マシンがあり、再帰的に列挙可能な言語には停止しないチューリング マシンがあることを知っています。

問題は、言語が再帰的か、再帰的に列挙可能か、またはどちらでもないかを判断するための迅速な基準があるかということです。たとえば、言語が文脈自由であることを理解するために PDA を構築する必要はありません。1 つのスタックが必要であるという事実からはわかりません。問題に対する同様の迅速なアプローチはありますか (チューリング マシンを構築する手間が省けることを願っています)。

アマゾンでスティーブン・ウルフラムの「新しい種類の科学」のレビューを読んでいるときに、私は次の声明に出くわしました。

すべてのコンピュータサイエンス（CS）の学生は、チューリングマシン（TM）などのユニバーサルコンピュータで可能なすべてのプログラムを体系的に一覧表示して実行する非常に単純な2行のプログラムであるdovetailerを知っています。

誰かが「dovetaling」を説明する「単純な2行のプログラム」を与えることができますか？

これについてどうやって行くかについて私にいくつかのアイデアを教えてください

少なくとも4つの重要な（つまり、拒否されない）状態と少なくとも6つの重要な（つまり、拒否されない）遷移を持つチューリングマシンを（Sipser表記を使用して）描画します。

私は正規表現を与えられました、そして私はそれをNFAそしてDFAに隠蔽することになっています。正規表現は次のとおりです。

a（b | c）* a | aac * b

次に、トムソンのアルゴリズムを使用してこれをNFAにカバーしました。

これがDFAです。

誰かが私が間違っているか正しいかを私に知らせてください。

このDFAを最小化しようとしています：http：//img145.imageshack.us/img145/3006/dfac.png

これが私の最小化されたDFAです：http：//img195.imageshack.us/img195/4131/mdfa.png

私は正しいですか？ありがとう

PS-これは宿題です。宿題について話し合うことができます。私は答えを求めていません。ステートマシンを扱うのはこれが初めてなので、自分が正しい方向に進んでいるかどうかを知りたいだけです。

言語L={1 ^ 200}、またはむしろ、200個の1が連続するような言語？別名、このTMは、200個の「1」を連続して受信した場合にのみ受け入れます。したがって、これを解決するには200の状態が必要でしょうか、それともより少ない状態で単純化できるでしょうか。

TMがどのように機能するかを理解するのに役立つようにこれを求めています。

注：アルファベットは{1}になります。TMは、必要な数のテープを使用できます。

G の言語が nil であるような文脈自由文法 G がある場合、G は決定可能ですか?

答えがイエスであることはわかっていますが、これを証明するのに苦労しています。私が最初に考えたのは、q1 という 1 つの状態しかないということです。これは、G に相当するチューリング マシンの開始状態と受け入れ状態です。このマシンは、入力を受け入れず、受け入れに達したため、すぐに停止して受け入れます。州。これは受け入れられる答えですか、それとも私はここから離れていますか?

編集：

Joel が以下で述べたように、私が説明した言語はすべての文字列を受け入れます。これに対抗するために、私は 2 番目のマシン G' を提案します。G' には、開始状態 q1、受け入れ状態 q2、拒否状態 q3 の 3 つの状態があります。q1 は G' のアルファベットのすべてのシンボルで q3 に遷移し、q2 も同様です。q1 から q2 へのイプシロン遷移があります。したがって、G' に供給される文字列に記号が存在する場合、G' は拒否します。シンボルがない場合、唯一のオプションはイプシロン遷移を受け入れ状態にすることです。それはどのように聞こえますか？

編集：

上記の解は、言語 L(G') = {""} を受け入れることが証明されました。

ターニング マシンについて非常に簡単な質問があります。

実行する最初のアクションにテープの巻き戻しが含まれる場合、開始点を過ぎて戻るのでしょうか、それともこれは特殊なケースであり、開始点にとどまりますか?

両端の文字を (Φ) に置き換える回文を見つけるのは非常に簡単です。

a を A に変更し、タスクの最後に A を a に変更することで可能です。しかし、追加の記号を使用せずにこれを達成する方法を知っている人はいますか?

JFLAPでチューリングマシンを構築しました。これはバイナリ加算器です。これは3テープTMです。最初の2つのテープが入力で、3番目のテープが出力を取得します。バッチテストを実行しようとすると（情報はここにあります）、.txtファイルの3番目の文字列を出力テープにすることができません。私の.txtファイルは次のように作成されています。

ただし、これは3テープマシンである必要があるため、出力文字列にしたい最後のバイナリ文字列を3番目の入力文字列として使用します。これは、すべてのテストで空白にする必要があります。JFLAPが最後の文字列が出力であることを理解するようにテスト文字列をフォーマットする方法はありますか？