c++ - 正则表达式算法 - 组合或

Question

我正在开发一个 C++ 应用程序来首先解析正则表达式字符串，然后用它执行一些计算。是否有任何现有的算法可以输出可以被给定正则表达式识别的长度为 L 的字符串的数量 N，例如 (a|ab)* | (aa|bb)* ?或者是否有我可以使用的数学公式，例如涉及阶乘的数学公式？我只想获得可以由给定数字 L 的此类正则表达式短语识别的字符串数 N。例如 (a|ab)*正则表达式可以识别多少长度为 5 (L) 的字符串。我认为答案是 5。但是对于大量的 L，我想知道是否有任何算法或数学表达式可以计算出来。

Answer 1

这是一种基于矩阵求幂的高效算法，您可以使用它来计算这些数字。

我只会给出一个高层次的描述，而不是代码。

首先，您想使用计算机科学基础中众所周知的等价关系，即(简单)正则表达式等价于有限状态机。

(回想一下，有限状态机本质上是一个流程图，其中从每个节点开始，字母表中的每个字母都有一个标记的边到某个特定的其他节点(或者可能是一个循环)。此外，某些子集状态被称为“接受集”，流程图中的一些特定状态是开始状态。在有限状态机中，一个字符串被称为诱导路径，通过从开始状态开始并连续跟随标记的边。如果最终状态在接受集中，机器 accepts 一个字符串，否则 rejects 一个字符串。
一个经典的构造表明，我们可以从任何正则表达式构造一个相似大小的有限状态机，并且从任何有限状态机我们可以构造一个相似大小的正则表达式。与正则表达式对应的任何语言(所有有限字符串的子集)都称为“正则”，并且当且仅当它对应于有限状态机时，语言才是正则的。)

例如，如果我有一个字母 {a,b,c} ，以及正则表达式 (a|b)* ，它对应于具有两种状态的机器。开始状态有一个标记为 a 的循环，一个标记为 b 的循环，和一个标记为 c 的箭头到第二个状态。第二个状态本身有三个循环，所以如果你去那里你会被困住。接受集仅包含开始状态。

程序的第一步是将正则表达式转换为相应的有限状态机。 (可能一些现有的正则表达式库已经基本上做到了这一点，我认为 PCRE 可能，虽然我不确定。)

给定一个有限状态机，我想构造一个相应的随机矩阵。在这个矩阵中，每个状态都有一行，每个状态都有一列，每个条目都是一个概率。概率p_{i,j}在条目 (i,j) , 等于如果我处于状态 i 的概率，我随机读了一封信，我去状态j下一个。所以对于我给出的例子，矩阵是

[ 2/3 1/3 ]
[ 0 1 ]

如果您想了解长度为 k 的字符串，然后使用矩阵求幂，计算矩阵 M^k哪里M是上面的概率转移矩阵。

最后，如果 q是开始状态，将所有条目相加M^k_{q, s}每个州s在接受集中。这些概率的总和恰好等于长度为 k 的随机字符串的概率。被正则表达式接受。因此，您可以通过乘以 N^k 来获得此类字符串的数量。哪里N是字母表中的字母数。

我认为这个算法的存在并不难，但也不是微不足道的，我曾经在计算理论课的期末考试中给出了一个更难的版本作为额外的学分问题。我不知道它的任何现有实现，有兴趣知道。

当您使用矩阵求幂时，通过这种方式比朴素的方法有一些显着的加速。这允许您为大型 k 执行此操作迅速地。

不知道有没有更高效、更近似的解决方案，会很有趣。我猜随机抽样总会给你一些东西，但也许有某种频谱算法，基于对矩阵进行奇异值分解 M或者其他的东西。

注意:如果你真的要实现它，我猜你不应该使用浮点数，矩阵M实际上应该是一个整数矩阵。基本上你会把它乘以 N哪里N是字母表中的字母数。您可以跳过将总和乘以 N^k之后。我认为使用概率更容易理解，但在那个版本中，M^k_{i,j}只是在数 number of paths from i to j of length k .

注意:正如评论中所指出的，该算法是 k 位数的多项式对于任何固定的正则表达式，即使对于大型 k 也很好.尽管正则表达式的大小在最坏的情况下是指数级的——为了处理大而复杂的正则表达式，我想如果你想使用这种方法，你应该使用某种 DFA 最小化。对于问题中显示的简单正则表达式，我认为应该没问题。