我正在开发一个软件来从正则表达式生成一个图灵机。
[ 编辑：为了澄清，OP希望将正则表达式作为输入，并以编程方式生成图灵机来执行相同的任务。OP 正在寻求执行从正则表达式创建 TM 的任务，而不是使用正则表达式。]
首先，我将解释一下我做了什么，然后我的具体问题是什么：
我将正则表达式建模如下：
正则表达式（接口）：下面的类实现了这个接口
简单（即：“aaa”、“bbb”、“abcde”）：这是一个叶类，它没有任何子表达式
ComplexWithoutOr (ie: "a(ab)*","(a(ab) c(b) )*")：这个类包含一个正则表达式列表。
ComplexWithOr (ie: "a(a|b) ","(a((ab) |c(b) ) ")：该类包含一个Or运算，其中包含一个RegularExpression的列表。它表示“a|b " 第一个例子的一部分和第二个例子的 "(ab) |c(b) "。
变量（即：“awcw”，其中 w E {a,b}*）：尚未实现，但想法是将其建模为具有与 Simple 不同的逻辑的叶类。它代表示例的“w”部分。
理解并同意上述模型很重要。如果您有任何问题，请在继续阅读之前发表评论...
在 MT 生成方面，我有不同程度的复杂性：
很简单：这种表达方式已经在起作用了。为每个字母生成一个新状态并向右移动。如果在任何状态下，读取的字母不是预期的，它就会启动一个“回滚电路”，在 MT 磁头处于初始位置时结束，并在非最终状态下停止。
ComplexWithoutOr：我的问题来了。在这里，算法为每个子表达式生成一个 MT 并将它们连接起来。这适用于一些简单的情况，但回滚机制有问题。
这是一个不适用于我的算法的示例：
“(ab) abac”：这是一个 ComplexWithoutOr 表达式，它包含一个 ComplexWithOr 表达式“(ab) ”（在“ab”内有一个 Simple 表达式）和一个 Simple 表达式“abac”
我的算法首先为“ab”生成一个 MT1。这个 MT1 被 MT2 用于“(ab)*”，所以如果 MT1 成功则再次进入 MT1，否则 MT1 回滚，MT2 正确完成。换句话说，MT2 不能失败。
然后，它为“abac”生成一个 MT3。MT2的输出就是MT3的输入。MT3的输出是执行的结果
现在，假设这个输入字符串：“abac”。如您所见，它与正则表达式匹配。因此，让我们看看执行 MT 时会发生什么。
MT1 第一次执行“ab”。MT1 第二次“ac”失败并回滚，将 MT 头置于第三位置“a”。MT2 正确完成并将输入转发到 MT3。MT3 失败，因为 "ac"!="abac"。所以 MT 不识别“abac”。
你明白这个问题吗？你知道有什么解决办法吗？
我是用Java开发的，但是语言不重要，我想讨论一下算法。