一对连续的 0 和一对连续的 1 的二进制字符串的正则表达式

Question

1*(011*)*00(11*0)* 1* intersect 0*(100*)*11(00*1)* 0*

正则表达式的前半部分应匹配具有一对连续 0 的所有二进制字符串，后半部分应匹配具有一对连续 1 的所有二进制字符串。由于第一个包含一对连续的 1 的字符串，第二个包含一对连续的 0 的字符串，我声称整个正则表达式只会匹配最多一对连续的 0 和一对连续的 1 的二进制字符串.这个对吗？

Answer 1

是的，但更准确地说，您的表达式匹配包含恰好一对 0 和恰好一对 1（而不是 "at most"）的二进制字符串。

我可以用这个方法证明：

这是另一个对这些语义进行编码的正则表达式，使用并集而不是交集，我觉得这样更直接。

(1)?(01)*00(10)*11(01)*(0)?|(0)?(10)*11(01)*00(10)*(1)?

前半部分匹配一对零在一对一之前的二进制字符串，后半部分匹配一对零在一对零之前的二进制字符串。在这些对之前、之后和之间可能会出现交替值。

如果一个字符串与这些模式中的任何一个匹配（而不是在您的表达式中都匹配），则该字符串被接受。

现在，可以根据这些正则表达式中的任何一个构造状态转换。我在下面这样做了，首先是我的，然后是你的。每个编号状态都包含一个正则表达式列表，这些正则表达式描述字符串的剩余部分，以及遇到 0、1 或 end-of-line 时发生的状态转换。如果字符串与列表中的任何正则表达式匹配，则该字符串匹配。

如你所见，你的版本和我的版本之间的状态转换是完全同源的。因此，它们代表完全相同的一组字符串。

start    (1)?(01)*00(10)*11(01)*(0)?
         (0)?(10)*11(01)*00(10)*(1)?
     0    1
     1    2
     EOL    NO_MATCH
1        1(01)*00(10)*11(01)*(0)?
         0(10)*11(01)*(0)?
         (10)*11(01)*00(10)*(1)?
     0    3
     1    2
     EOL    NO_MATCH
2        (01)*00(10)*11(01)*(0)?
         0(10)*11(01)*00(10)*(1)?
         1(01)*00(10)*(1)?
     0    1
     1    4
     EOL    NO_MATCH
3        (10)*11(01)*(0)?
     0    NO_MATCH
     1    5
     EOL    NO_MATCH
4        (01)*00(10)*(1)?
     0    6
     1    NO_MATCH
     EOL    NO_MATCH
5        0(10)*11(01)*(0)?
         1(01)*(0)?
     0    3
     1    7
     EOL    NO_MATCH
6        1(01)*00(10)*(1)?
         0(10)*(1)?
     0    8
     1    4
     EOL    NO_MATCH
7        (01)*(0)?
     0    9
     1    NO_MATCH
     EOL    MATCH
8        (10)*(1)?
     0    NO_MATCH
     1    10
     EOL    MATCH
9        1(01)*(0)?
     END
     0    NO_MATCH
     1    7
     EOL    MATCH
10       0(10)*(1)?
     END
     0    8
     1    NO_MATCH
     EOL    MATCH

start    1*(011*)*00(11*0)*1* + 0*(100*)*11(00*1)*0*
     0    1
     1    2
     EOL    NO_MATCH
1        11*(011*)*00(11*0)*1* + 0*(100*)*11(00*1)*0*
         0(11*0)*1* + 0*(100*)*11(00*1)*0*
     0    3
     1    2
     EOL    NO_MATCH
2        1*(011*)*00(11*0)*1* + 00*(100*)*11(00*1)*0*
         1*(011*)*00(11*0)*1* + 1(00*1)*0*
     0    1
     1    4
     EOL    NO_MATCH
3        (11*0)*1* + 0*(100*)*11(00*1)*0*
     0    NO_MATCH
     1    5
     EOL    NO_MATCH
4        1*(011*)*00(11*0)*1* + (00*1)*0*
     0    6
     1    NO_MATCH
     EOL    NO_MATCH
5        1*0(11*0)*1* + 00*(100*)*11(00*1)*0*
         (11*0)*1* + 00*(100*)*11(00*1)*0*
         1*0(11*0)*1* + 1(00*1)*0*
         (11*0)*1* + 1(00*1)*0*
     0    3
     1    7
     EOL    NO_MATCH
6        11*(011*)*00(11*0)*1* + 0*1(00*1)*0*
         0(11*0)*1* + 0*1(00*1)*0*
         11*(011*)*00(11*0)*1* + 0*
         0(11*0)*1* + 0*
     0    8
     1    4
     EOL    NO_MATCH
7        1*0(11*0)*1* + (00*1)*0*
         1* + (00*1)*0*
     0    9
     1    NO_MATCH
     EOL    MATCH
8        (11*0)*1* + 0*1(00*1)*0*
         (11*0)*1* + 0*
     0    NO_MATCH
     1    10
     EOL    MATCH
9        (11*0)*1* + 0*1(00*1)*0*
         (11*0)*1* + 0*
     0    NO_MATCH
     1    7
     EOL    MATCH
10       1*0(11*0)*1* + (00*1)*0*
         1* + (00*1)*0*
         (11*0)*1* + 0*
     0    8
     1    NO_MATCH
     EOL    MATCH

一对连续的 0 和一对连续的 1 的二进制字符串的正则表达式

A regular expression for a binary string with one pair of consecutive 0s and one pair of consecutive 1s

regex

regular-language