正規表現からチューリング マシンを生成するソフトウェアを開発しています。
[ 編集: 明確にするために、OP は正規表現を入力として受け取り、同じタスクを実行するためにチューリング マシンをプログラムで生成したいと考えています。OPは、正規表現を使用するのではなく、正規表現からTMを作成するタスクを実行しようとしています。]
最初に、私が行ったことを少し説明し、次に私の問題を説明します。
次のように正規表現をモデル化しました。
RegularExpression (インターフェース): 以下のクラスはこのインターフェースを実装します
単純 (例: "aaa"、"bbb"、"abcde"): これは部分式を持たないリーフ クラスです。
ComplexWithoutOr (例: "a(ab)*","(a(ab) c(b) )*"): このクラスには、RegularExpression のリストが含まれます。
ComplexWithOr (つまり: "a(a|b) ","(a((ab) |c(b) ) "): このクラスには Or 演算が含まれ、RegularExpression のリストが含まれます。これは、"a|b最初の例の " の部分と、2 番目の例の "(ab) |c(b) " です。
変数 (つまり: "awcw"、ここで w E {a,b}*): これはまだ実装されていませんが、Simple とは異なるロジックを持つリーフ クラスとしてモデル化することを目的としています。例の「w」の部分を表します。
上記のモデルを理解し、同意することが重要です。質問がある場合は、続きを読む前にコメントしてください...
MT 生成に関しては、さまざまなレベルの複雑さがあります。
簡単です。このタイプの式はすでに機能しています。文字ごとに新しい状態を生成し、右に移動します。いずれかの状態で、読み取られた文字が予期されたものではない場合、「ロールバック回路」が開始され、MT ヘッドが初期位置で終了し、最終状態ではない状態で停止します。
ComplexWithoutOr: ここに私の問題があります。ここで、アルゴリズムは部分式ごとに MT を生成し、それらを連結します。これはいくつかの単純なケースでは機能しますが、ロールバック メカニズムに問題があります。
私のアルゴリズムではうまくいかない例を次に示します。
"(ab) abac": これは、ComplexWithOr 式 "(ab) " ("ab" 内に Simple 式を持つ) と Simple 式 "abac" を含む ComplexWithoutOr 式です。
私のアルゴリズムは、最初に "ab" の MT1 を生成します。この MT1 は "(ab)*" のために MT2 によって使用されるため、MT1 が成功すると MT1 に再び入ります。つまり、MT2は失敗できません。
次に、「abac」の MT3 を生成します。MT2のアウトプットがMT3のインプットです。MT3の出力は実行結果です
ここで、この入力文字列を「abac」とします。ご覧のとおり、正規表現と一致します。では、MT を実行するとどうなるか見てみましょう。
MT1 は最初の "ab" で実行されます。MT1 は 2 回目の "ac" で失敗し、ロールバックして、MT ヘッドを 3 番目の位置 "a" に置きます。MT2は正しく終了し、入力はMT3に転送されます。"ac"!="abac" のため、MT3 は失敗します。したがって、MT は「abac」を認識しません。
問題を理解していますか？これに対する解決策を知っていますか？
私は Java を使用して開発していますが、言語は重要ではありません。アルゴリズムについて説明したいと思います。