Регулярное выражение для двоичной строки с одной парой последовательных 0s и одной парой последовательных 1s

Question

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

Первая половина регулярного выражения должны соответствовать все двоичные строки с одной парой последовательных 0s, а вторая половина должна соответствуют всем двоичным строкам с одной парой последовательных 1s. Поскольку первый содержит строки с одной парой последовательных 1s, а второй содержит строки с одной парой последовательных 0s, я утверждаю, что все регулярное выражение будет соответствовать только двоичным строкам, причем не более одной последовательной пары 0s и одной последовательной пары из 1s , Это верно?

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