是否可以编写Perl/Java/etc正则表达式来匹配十进制(非)素数？

Question

相关问题/材料:

• 我们如何匹配^ nb ^ n与Java正则表达式？

• 如何确定一个数字是否是正则表达式的素数？(它涉及一元素数匹配,而我正在寻找≥2的基数;不过是一个很好的伎俩,是什么让我思考这个)

• http://nikic.github.io/2012/06/15/The-true-power-of-regular-expressions.html

众所周知,由各种编程语言支持的"正则表达式"生成在形式意义上非常规的语言,并且如上述材料所示,能够识别至少一些上下文敏感语言.

语言L = {x | x是基数10中的素数.}是一种上下文敏感语言,因为素数可以通过线性有界自动机来测试(但它不是通过泵浦引理参数的无上下文语言).

那么,是否可以编写一个Perl或Java正则表达式,它恰好接受基数为10的所有素数？如果感觉更容易,可以随意替换≥2的任何其他基础或精确识别所有复合数字.

例如,使用转义来运行任意Perl代码被视为作弊.重复替换(很容易图灵完成)也超出了范围; 整个工作应该在正则表达式内完成.这个问题更多的是关于正则表达式实际有多强大的界限.

Answer 1

注意：这些正则表达式是为 PHP 编写的，并使用所有格量词，这些量词在许多但不是所有语言中使用，例如 java-script 不支持它们。而且，这是非常低效的，并且很快就会变得不可行。

编辑：这里是基数 10，\b(((\d)(?=[\d\s]*(\4{0,10}(n(?=.*n\3)|nn(?=.*1\3)|n{3}(?=.*2\3)|n{4}(?=.*3\3)|n{5}(?=.*4\3)|n{6}(?=.*5\3)|n{7}(?=.*6\3)|n{8}(?=.*7\3)|n{9}(?=.*8\3))?)))+)(?![\d\s]*(n(?=\4))++(..?1|(...*)\8+1))在此之后我使用了基数 2，以使事情变得更容易。

编辑：这个将允许您传递一个包含多个二进制数的字符串并匹配那些素数它\b(((\d)(?=[\d\s]*(\4{0,2}n(?=.*\3)|\4{0,2})))+)(?![\d\s]*(n(?=\4))++(..?1|(...*)\7+1)) 基本上是通过使用边界 \b 而不是字符串 ^ 的开头来实现这一点的，它允许在前进时使用任意数量的小数和空格ns 并将测试基数为 1 的表示形式的整个部分包装在负前瞻中。除此之外，它的工作方式与下面的相同。作为示例1111 1011 nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn1 将匹配1011.

我已经设法得到一些我认为有效的东西（检查到 25）并且它与非素数匹配。这里是基数 2（更容易解释），^((\d)(?= \d*\s(\3{0,2}n(?=.*\2)|\3{0,2})))+\s(n(?=\3))*+\K(..?1|(..+?)\6+1)可以扩展到基数 n，但这会非常快地扩展正则表达式。为了让这个正则表达式工作，我需要一些额外的条件（有点hacky），输入字符串必须是数字，后跟一个空格，后跟至少与您的数字值一样多的n个字符（如果您有数字10（您需要在其后至少 10 ns）后跟您的基数数字，按顺序排除您的 0 数字（例如基数 10 123456789），不包括您的 0。例如11 nnnnnnnnnnnnnn1. 这是因为正则表达式没有可访问的存储空间，因此我需要使用捕获组来执行此操作。最后，这个正则表达式使用 /x 来忽略表达式中的空格，如果您不想使用它，则删除所有空格。

现在我将分 3 个步骤解释其工作原理。该正则表达式分为 3 部分：

第 1 部分：这部分将基数 n > 1 更改为基数 1 作为 ns 的捕获组

这部分^((\d)(?= \d*\s(\3{0,2}n(?=.*\2)|\3{0,2})))+的工作原理与a^nb^n问题中的示例非常相似。前面的 ^ 表示完整的比赛必须从头开始，这对于后面的比赛很重要。该代码的主要结构是^((\d)(?= \d*\s (suff)))+这获取开始和第一个空格之间的每个小数，并使用 (\d)(?=) 执行正向前瞻，其中 \d 是小数，(?=) 是前瞻\d 位于()稍后的捕获组中。这是我们当前正在查看的数字。

前瞻的内部实际上并不是检查前面的条件，而是建立一个捕获组来表示基数 1 中的数字。捕获组的内部如下所示

\d*\s(\3{0,2}n(?=.*\2)|\3{0,2})) 

\d*\s 部分基本上将我们正在查看的字符移动到剩余数字 \d* 的其余部分（\d 是数字，* 是 0 到 n 尽可能多的次数），现在让我们看开头ns。

(\3{0,2}n(?=.*\2)|\3{0,2}))

是一个自引用捕获组，这里需要您在末尾输入的数字。该组匹配自身 0 到 2 次，但尽可能多的次数（使用 \3{0,2} 和 \3 表示包含组 3 和 {0,2} 表示匹配 0 到 2 次）这意味着如果当前数字之前有一个数字，则其以 1 为基数的表示形式将乘以 2。对于基数 10 来说，这将是 10，对于基数 16 来说，这将是 16 .如果这是第一个数字，则该组将是未定义的，因此它将匹配 0 次。然后，它根据匹配我们当前正在处理的数字（使用其捕获组）添加单个 n 或不添加 n。它通过使用正向前瞻来查找我们放置数字的输入末尾，n(?=.*\2) 如果它可以找到我们正在处理的数字后面的任何内容，则它与 n 匹配。这使得它能够识别我们此时正在处理的数字。（我会使用后视，但它们的长度是固定的）如果你有基数 3 并且想检查你当前正在处理的数字是否是 2，你会使用 nn(?=.*1\2) 这将匹配 nn仅当数字为二时。我们使用了或运算符“|” 对于所有这些，如果没有找到数字，我们假设它是 0 并且不添加 ns。由于它位于捕获组中，因此该匹配将保存在该组中。

总结这一部分，我们所做的就是让每个数字向前看，取前一个数字的基数 1 表示（保存在捕获组中），并将其乘以基数，然后匹配它，然后将其添加到基数 1 表示数字并将其保存在组中。如果依次对每个数字执行此操作，您将得到该数字的基数表示形式。让我们看一下例子。第101章

首先它转到 sat 因为^。所以：101 nnnnnnnnnnnnnnnnn1

然后它转到第一个数字并将其保存在捕获摸索中 1 01 nnnnnnnnnnnnnnnnn1

第2组：1

它使用 \d*\s 进行前瞻来跳过所有数字和第一个空格。1 01 n nnnnnnnnnnnnnnnn11

现在位于捕获组 3 内

它采用此上限组的先前值并匹配它 0 到 2 次

由于未定义，因此匹配 0 次。

现在，它再次向前查找，尝试查找与捕获组 2 1 01 n nnnnnnnnnnnnnnnn中的数字匹配的数字1

因为已经发现它匹配捕获组 3 2 1 01 nn nnnnnnnnnnnnnnn1中的 1 n

现在它离开组 3，更新其值并离开前瞻组 3 = n

现在，它查看下一个数字并将其保存在捕获组 1 0 1 nnnnnnnnnnnnnnnnn1中

组 2 = 0

组 3 = n

然后，它还使用前瞻并转到第一个 n 1 0 1 n nnnnnnnnnnnnnnnn1

然后它匹配组 3 0 到 2 次，但尽可能多，所以 n 1 0 1 nn nnnnnnnnnnnnnnn1

然后，它使用前瞻尝试匹配组 2 中的数字（它可以这样做），因此在从组 3 和前瞻返回之前，它不会添加 ns

组 3 = nn

现在，它查看下一个数字并将其保存在组 2 10 1 nnnnnnnnnnnnnnnnn1 使用前瞻功能，它会转到 ns 的开头并匹配 2 次 group 3 10 1 nnnn nnnnnnnnnnnnn1 然后它使用前瞻功能来尝试匹配它找到的第 2 组中的数字与 an 匹配，并从第 3 组和前瞻中返回。group3 = nnnnn 第 3 组现在包含我们的数字的以 1 为基数的表示形式。

第 2 部分将 ns 减小到以 1 为底的数字表示形式的大小

\s(n(?=\3))*+\K

这会匹配空格，然后匹配 ns，只要您可以匹配前面的组 3（数字的基本表示形式）即可。它通过使用所有格 *+ 尽可能多地匹配 n 来实现这一点（它永远不会放弃匹配，这是为了阻止匹配稍后被缩小以使匹配起作用） n 具有积极的前瞻能力 n (?=\3) 这意味着只要前面有组 3，n 就会被匹配（\3 给出捕获组 3）。这给我们留下了以 1 为基数的表示形式，而数字是唯一不匹配的。然后我们使用 \K 表示从这里重新开始匹配。

第三部分 我们现在使用问题中提到的相同算法来获取素数，但我们强制它在表示基数的开头和数字的开头之间不匹配。您可以在此处阅读其工作原理如何使用正则表达式确定一个数字是否为素数？

最后，要将其变成基础正则表达式，您必须做一些事情

 ^((\d)(?= \d*\s(\3{0,2}n(?=.*\2)|\3{0,2})))+\s(n(?=\3))*+\K(..?1|(..+?)\6+1)

首先在输入字符串的末尾添加更多数字，然后更改 n

?=.*\2 to  n?=.*n\2 |  n?=.*1\2   n?=.*3\2 ..,  n?=.***n**\2

最后将 \3{0,2} 更改为 \3{0, n }。其中n是基数。另请记住，如果没有正确的输入字符串，这将无法工作。