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

我正在开发一个软件来从正则表达式生成图灵机。从正则表达式生成图灵机的算法

[编辑：为了阐明，OP想要采用正则表达式作为输入，并以编程方式生成图灵机来执行相同的任务。 OP正在寻求执行从正则表达式创建TM 的任务，而不是使用正则表达式的。 ]

首先，我将解释一下我做了什么，然后什么是我的具体问题：我建模的正则表达式如下

：

正则表达式（接口）：下面的类实现了这个接口

简单（即： “AAA”， “BBB”， “ABCDE”）：这是叶类是没有任何子表达式

ComplexWithoutOr（即： “A（AB）*” ，“（a（ab）c（b））*“）：这个类包含一个RegularExpression列表。

ComplexWithOr（即： “一个（A | B）”， “（一（（AB） | C（B））”）：这个类包含一个或者操作，其中包含正则表达式的列表，代表第一个例子的“a | b”部分和第二个例子的“（ab）| c（b）”

变量（即：“awcw”，其中w E {a ，b} *）：这还没有实现，但是我们的想法是将它建模为一个具有与Simple不同的逻辑的叶类，它代表了示例中的“w”部分。

重要的是，您理解一个d同意上面的模型。如果您有问题作出评论之前，继续阅读...

当谈到MT一代，我都有不同程度的复杂性：

简单：这种类型的表达式已经工作。为每个字母生成一个新状态并向右移动。如果在任何状态下，读取的字母不是预期的，它会启动一个“回滚电路”，在MT头处于初始位置时结束并停止在非最终状态。

ComplexWithoutOr：这里是我的问题。在这里，算法为每个子表达式生成一个MT并将它们连接起来。这适用于一些简单的情况，但我遇到了回滚机制问题。

这里是不与我的算法工作的一个例子：

“（AB）ABAC”：这是一个包含ComplexWithOr表达式“（AB）”一ComplexWithoutOr表达（即有一个简单的“ab”中的表达式）和简单表达式“abac”

我的算法首先生成“ab”的MT1。这个MT1被MT2用于“（ab）*”，所以如果MT1成功，它将再次进入MT1，否则MT1回滚和MT2结束。换句话说，MT2不会失败。

然后，它生成“abac”的MT3。 MT2的输出是MT3的输入。MT3的输出是执行的结果

现在，让我们假设这个输入字符串：“abac”。正如你可以看到它与正则表达式匹配。所以让我们看看MT执行时会发生什么。

MT1第一次被执行“ab”。 MT1第二次“失败”并回滚失败，将MT头放在第三位“a”。 MT2完成正确并且输入被转发到MT3。 MT3失败，因为“ac”！=“abac”。所以MT不承认“abac”。

你明白这个问题吗？你知道这个解决方案吗？

我使用Java开发它，但语言不重要，我想讨论一下这个算法。

来源

2010-07-02 Neuquino

如果一个正则表达式可以构造一个图灵机，它仍然被认为是一个正则表达式？ – kennytm 2010-07-02 18:49:59

你确定它是你正在生产的全部图灵机，而不是非确定性有限状态机吗？这可以通过结合NDFAs，或者甚至将它们转换为确定性的FSA来解决。基本上FSA从第一个和第二个表达式维护一个状态的能量，因为“abac”中的最初“ab”可以在任何一个中。 – mdma 2010-07-02 18:54:37

我正在尝试结合使用FSA。我希望找到一种方法，无需重写（或转换）正则表达式。但是，是的，检测一些表达是否在另一个表达应该帮助。谢谢你的提示。 – Neuquino 2010-07-02 19:11:45

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

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

来源

2010-07-03 14:45:28 MAK

谢谢@MAK，这些系列文章非常有帮助。现在我试图将用户的正则表达式重写为更简单的（但是等价的）。那么我可以使用我的算法来生成TM。我认为，重写正则表达式，应该有可能避免这个问题，我现在堆栈。 – Neuquino 2010-07-05 13:47:55

@Neuquino：请注意，所有适当的正则表达式都可以简化为仅使用符号'* +？|。。'和文字字符的正则表达式。所以，如果你的算法可以使用更简单的符号集为正则表达式创建TM/FSM，它基本上和任何正则表达式引擎一样好。 – MAK 2010-07-05 14:15:44

你知道是否有任何图书馆或源代码，使减少？或者至少，有些理论认为“所有适当的正则表达式可以简化为只使用符号* +？|。和文字字符”的说法是基于此的，所以我可以构建一个算法来减少输入正则表达式。 – Neuquino 2010-07-05 20:14:33

在乔姆斯基层次结构中，正则表达式是Level3，而TM是Level1。这意味着，TM可以产生任何正则表达式，但反之亦然。

来源

2010-07-02 18:55:44 guest

如果我给你任何正则表达式，你可以生成一个识别该语言的TM。我想让这个过程自动化。 “来自”的“ – Neuquino 2010-07-02 19:05:14

”不是“使用”。 OP想要将正则表达式作为输入，并以编程方式生成图灵机来执行相同的任务。 OP正在寻求执行从正则表达式创建TM的任务，而不是使用正则表达式。 – CPerkins 2010-07-03 13:09:28

迈克尔Sipser，在Introduction to the Theory of Computation，在第1章中证明正则表达式等价于有限自动机的描述能力。证明的一部分涉及构造一个非确定型有限自动机（NDFA），它识别特定正则表达式描述的语言。我不打算复制该章节的一半，由于使用了该标记，这将非常困难，所以我建议您借阅或购买书籍（或者使用这些术语的Google搜索可能会出现类似的证据），并使用该章节证明作为算法的基础。

由于图灵机可以模拟NDFA，我假设一个生成NDFA的算法已经足够好了。

来源

2010-07-03 14:56:02 Confusion

谢谢@Confusion。我下载了这本书的数字版本。在这些日子里，我将开始阅读它。 – Neuquino 2010-07-05 13:50:33

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

回答

相关问题