正则表达式定义某些二进制序列

Question

正则表达式定义某些二进制序列

7

你如何编写一个正则表达式来定义所有由0和1组成的字符串，这些字符串在二进制数中表示的整数是3的倍数。

一些有效的二进制数包括：

- Jaelebi

4

这是你的计算理论作业吗？ - BobbyShaftoe

也许您可以提供一些背景信息，比如您想要做什么以及使用哪种编程语言。 - Tim Büthe

一部分。我认为我有正确的NFA，但似乎无法消除中间步骤，因为它非常复杂。 - Jaelebi

1

得到它。答案是 (1(01*0)*1)0。 - Jaelebi

4个回答

9

当你将一个数字除以三时，只有三种可能的余数（0、1和2）。你的目标是确保余数为0，因此是三的倍数。

这可以通过具有三个状态的自动机来完成：

ST0，3的倍数（0、3、6、9等）。

ST1，3的倍数加1（1、4、7、10等）。

ST2，3的倍数加2（2、5、8、11等）。

现在考虑任何非负数（这是我们的定义域），并将其乘以2（在末尾添加一个二进制零）。其转换如下：

ST0 -> ST0 (3n * 2 = 3 * 2n, still a multiple of three).
ST1 -> ST2 ((3n+1) * 2 = 3*2n + 2, a multiple of three, plus 2).
ST2 -> ST1 ((3n+2) * 2 = 3*2n + 4 = 3*(2n+1) + 1, a multiple of three, plus 1).

还可以考虑任何非负数，将其乘以二，然后在末尾添加一个二进制的1（加一）。其转换如下：

ST0 -> ST1 (3n * 2 + 1 = 3*2n + 1, a multiple of three, plus 1).
ST1 -> ST0 ((3n+1) * 2 + 1 = 3*2n + 2 + 1 = 3*(2n+1), a multiple of three).
ST2 -> ST2 ((3n+2) * 2 + 1 = 3*2n + 4 + 1 = 3*(2n+1) + 2, a multiple of three, plus 2).

这个想法是，在最后，你需要完成状态ST0。然而，由于可能存在任意数量的子表达式（和子子表达式），它不容易化简为正则表达式。

你需要做的是允许任何可以从ST0到ST0的转换序列，然后重复它们：

这些可以归结为两个RE序列：

ST0 --> ST0                                      :  0+
    [0]
ST0 --> ST1 (--> ST2 (--> ST2)* --> ST1)* --> ST0:  1(01*0)*1
    [1]     ([0]     ([1]    )* [0]    )* [1]

或正则表达式：

(0+|1(01*0)*1)+

这段代码捕获了三的倍数，至少是我测试的前十个。你可以尝试任意多的数字，它们都能正常工作，这就是数学分析的美妙之处，而不是凭经验判断。

- paxdiablo

我喜欢你的解释，顺便为那些阅读这个答案的人澄清一下，你需要在开头添加 ^ 才能得到一个有效的正则表达式。 - Holy semicolon

0

答案是(1(01*0)*10*)*，这是目前唯一适用于110011的答案。

- Thomas

-1

我不认为你会这样做。我无法相信在任何语言中使用正则表达式都是完成此任务的最佳方式。

- David Webb

我知道这不是最好的方法。我知道它可以完成，但我就是想不出怎么做。它涉及绘制自动机并消除中间状态。 - Jaelebi

3

@Dave Webb，你确实可以做到这一点。实际上，在计算机科学理论课程中，这是一种相当常见的练习，这就是为什么我不愿意回答这个问题的原因。 - BobbyShaftoe

@Dave Webb 答案是 (1(01*0)*1)0。 - Jaelebi

@unknowh 雅虎，不是完全正确的，那样对于 17 * 3 = 51（110011）是行不通的。您需要允许更多级别的重复。 - paxdiablo

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Qtax · Accepted Answer

使用这里提供的DFA，我们可以通过以下方式生成一个正则表达式，其中A、B、C代表DFA的状态。

A = 1B + 0A
B = 1A + 0C
C = 1C + 0B

C = 1*0B // Eliminate recursion

B = 1A + 0(1*0B)
B = 01*0B + 1A
B = (01*0)*1A // Eliminate recursion

A = 1(01*0)*1A + 0A
A = (1(01*0)*1 + 0)A
A = (1(01*0)*1 + 0)* // Eliminate recursion

导致生成类似以下的PCRE正则表达式：

/^(1(01*0)*1|0)+$/

Perl 测试/示例:

use strict;

for(qw(
11
110
1001
1100
1111
0
1
10
111
)){
    print "$_ (", eval "0b$_", ") ";
    print /^(1(01*0)*1|0)+$/? "matched": "didnt match";
    print "\n";
}

输出：

11 (3) matched
110 (6) matched
1001 (9) matched
1100 (12) matched
1111 (15) matched
0 (0) matched
1 (1) didnt match
10 (2) didnt match
111 (7) didnt match