私は、すべての正規言語が決定可能であることを証明しようとしています。
したがって、決定論的有限オートマトン (DFA) からチューリング決定可能マシンに移行できることを証明しようとしているのです。
そのため、元の自動化 (DFA) をシミュレートするチューリング マシンを構築する方法がわかりません。
状態 (自動化とチューリング マシン) はもちろん似ていますが、続行する方法がわかりません..
前もって感謝します。しらん
質問する
1645 次
1 に答える
2
これは機能しませんか : 入力テープには、認識される単語と、それに続く入力アルファベットの外側からの文字 # が含まれています。DFA の状態 q ごとに、遷移のあるチューリング マシンの状態 q があります。
input letter -> tape operation, next state, write symbol
c for each input letter -> move right, the state the DFA reaches from state q with letter c, write c
# -> STOP ACCEPT or STOP REJECT, depending on whether q is final in the DFA.
于 2013-11-24T20:09:18.510 に答える