从正则表达式生成图灵机的算法

Question

我正在开发一个软件，可以从正则表达式生成图灵机。换句话说，我想以正则表达式作为输入，并以编程方式生成图灵机来执行相同的任务。

这就是我所做的：

我对正则表达式进行了建模，如下所示：

• 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

。这个TM₁被TM₂用于

(ab)*

，所以如果TM₁成功，它会再次进入TM₁，否则TM₁回滚，TM₂成功完成。换句话说，TM₂不会失败。

然后，它为 _abac 生成 TM

3

。 TM₂的输出是TM₃的输入。 TM₃的输出就是执行结果。

现在，假设输入字符串：

abac

。正如您所看到的，它与正则表达式匹配。那么让我们看看执行 TM 时会发生什么。

TM₁第一次执行成功：

ab

。 TM₁

ac

第二次失败并回滚，将 TM 头置于 ^a 处的第 3

rd

位置。 TM₂ 成功完成，输入转发至 TM₃。 TM₃ 失败，因为

ac

与

abac

不匹配。所以TM不认识

abac

。

这是一个问题。怎么解决这个问题？

我使用Java来开发它，但它的语言并不重要。我的问题涉及算法。

Answer 1

我并不完全清楚你到底想实现什么。看起来您想要制作一个图灵机（或一般的任何 FSM），它只接受正则表达式也接受的那些字符串。实际上，您想要将正则表达式转换为 FSM。

实际上，这正是真正的正则表达式匹配器在幕后所做的事情。我认为 Russ Cox 的这系列文章涵盖了您想做的很多事情。

Answer 2

Michael Sipser 在《计算理论导论》中，在第一章中证明了正则表达式在描述能力上等同于有限自动机。证明的一部分涉及构建一个非确定性有限自动机 (NDFA)，该自动机可识别特定正则表达式所描述的语言。我不打算复制该章的一半，由于使用的符号，这会很困难，所以我建议你借用或购买这本书（或者使用这些术语进行谷歌搜索可能会找到类似的证明）并使用它证明作为算法的基础。 由于图灵机可以模拟 NDFA，我认为生成 NDFA 的算法就足够好了。

Answer 3