연속적인 0의 한 쌍의 연속 1S

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