一個正則表達式的二進制字符串與一對連續的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（而不是「至多」）。

我可以通過這種方法證明這一點：

這裏是另一個正則表達式來編碼這些語義，使用聯合而不是交叉路口，其感覺更簡單。

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

上半場匹配二進制串，其中該對的零的先於一對的那些，和第二半二進制串，其中該對的那些之前的一對零的匹配。在這些對之前，之後和之間可能會出現交替值。

如果字符串與這些模式中的任何一個匹配（而不是與您的表達式中的兩個匹配），則接受該字符串。

現在，可以基於這些正則表達式中的任何一個構造狀態轉換。我已經在下面做了，首先是我的，然後是你的。每個編號的狀態都包含一個正則表達式列表，用於描述字符串的剩餘部分，以及遇到0,1行或行尾時發生的狀態轉換。一個字符串匹配，如果它匹配列表中的任何正則表達式。如你所見，你的版本和我的版本之間的狀態轉換是完全同源的。因此，它們表示完全相同的一組字符串。

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