Une expression régulière pour une chaîne binaire avec une paire de 0 consécutifs et une paire de 1 consécutifs

Question

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

La première moitié de l'expression régulière doit correspondre à toutes les chaînes binaires avec une paire de 0 consécutifs et la seconde moitié devrait correspond à toutes les chaînes binaires avec une paire de 1 consécutives. Comme le premier contient des chaînes avec une paire de 1s consécutifs, et le second contient des chaînes avec une paire de 0 consécutifs, je prétends que toute l'expression régulière ne correspondrait qu'à des chaînes binaires avec au plus une paire de 0 et une paire consécutives de 1s . Est-ce correct?

Answer 1

Oui, mais plus précisément votre expression correspond à des chaînes binaires contenant exactement une paire de 0 et exactement une paire de 1 (plutôt que "au maximum").

je peux le prouver par cette méthode:

Voici une autre expression régulière pour coder cette sémantique, en utilisant une union plutôt que d'une intersection, que je me sens est plus simple.

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

La première moitié correspond à des chaînes binaires, dans lequel la paire de zéros précède la paire d'enfants, et la seconde moitié correspond à des chaînes binaires dans lequel la paire de ceux précède la paire de zéros. Avant, après et entre ces paires, des valeurs alternées peuvent apparaître.

Une chaîne est acceptée si elle correspond à l'un de ces modèles (plutôt que les deux comme dans votre expression).

Maintenant, il est possible de construire les transitions d'état basées sur l'une ou l'autre de ces expressions régulières. Je l'ai fait ci-dessous, d'abord avec le mien puis avec le vôtre. Chaque état numéroté contient une liste d'expressions régulières qui décrivent la partie restante de la chaîne et les transitions d'état qui se produisent lorsqu'un 0, un 1 ou une fin de ligne est rencontré. Une chaîne correspond si elle correspond à une expression régulière de la liste.

Comme vous pouvez le voir, les transitions d'état entre votre version et la mienne sont complètement homologues. Par conséquent, ils représentent exactement le même ensemble de chaînes.

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