我正在开发一个软件,可以从正则表达式生成图灵机。换句话说,我想以正则表达式作为输入,并以编程方式生成图灵机来执行相同的任务。
这就是我所做的:
我对正则表达式进行了建模,如下所示:
RegularExpression
(接口):下面的类实现了这个接口
Simple
(即:aaa
、bbb
、abcde
):这是一个叶类;它没有任何子表达式
ComplexWithoutOr
(即:a(ab)*
、(a(ab)*c(b)*)*
):此类包含 RegularExpression
的列表。
ComplexWithOr
(例如:a(a|b)*
、(a((ab)*|c(b)*)*
):此类包含一个 Or
操作,其中包含 RegularExpression
的列表。它代表第一个示例的 a|b
部分和第二个示例的 (ab)*|c(b)*
。
Variable
(示例:awcw
,其中 w ∈ {a,b}*):尚未实现,但其想法是将其建模为具有与 Simple
不同逻辑的叶类。它代表示例中的 w
部分。
当谈到图灵机(TM)生成时,我有不同程度的复杂性:
Simple
:这种表达方式已经可以发挥作用了。为每个字母生成一个新状态并向右移动。如果在任何状态下,读取的字母不是预期的,它就会启动一个“回滚电路”,以 TM 头处于初始位置结束并停止在非最终状态。
ComplexWithoutOr
:我的问题来了。该算法为每个子表达式生成一个 TM 并将它们连接起来。这适用于一些简单的情况,但我在回滚机制方面遇到问题。
这是我的算法失败的示例输入:
(ab)*abac
:这是一个 ComplexWithoutOr
表达式,其中包含 ComplexWithOr
表达式 (ab)*
(内部有 Simple
表达式:ab
)和 Simple
表达式 abac
我的算法首先为 ab
生成 TM
1。这个TM1被TM2用于
(ab)*
,所以如果TM1成功,它会再次进入TM1,否则TM1回滚,TM2成功完成。换句话说,TM2不会失败。
然后,它为 abac
生成 TM
3。 TM2的输出是TM3的输入。 TM3的输出就是执行结果。
现在,假设输入字符串:
abac
。正如您所看到的,它与正则表达式匹配。那么让我们看看执行 TM 时会发生什么。
TM1第一次执行成功:
ab
。 TM1 ac
第二次失败并回滚,将 TM 头置于 a
处的第 3rd位置。 TM2 成功完成,输入转发至 TM3。 TM3 失败,因为
ac
与 abac
不匹配。所以TM不认识abac
。
这是一个问题。怎么解决这个问题?
我使用Java来开发它,但它的语言并不重要。我的问题涉及算法。
我并不完全清楚你到底想实现什么。看起来您想要制作一个图灵机(或一般的任何 FSM),它只接受正则表达式也接受的那些字符串。实际上,您想要将正则表达式转换为 FSM。
实际上,这正是真正的正则表达式匹配器在幕后所做的事情。我认为 Russ Cox 的这系列文章涵盖了您想做的很多事情。