regex - Au plus deux paires de consecutives

Question

Je prends un cours de calcul qui enseigne aussi des expressions régulières. Il y a une question difficile à laquelle je ne peux pas répondre.

Trouvez une expression régulière pour la langue qui accepte les mots contenant au plus deux paires de 0 consécutifs. L'alphabet se compose de 0 et 1.

D'abord, j'ai fait un NFA du langage mais je ne peux pas le convertir en un GNFA (qui sera ensuite converti en regex). Comment puis-je trouver cet expressin régulier? Avec ou sans le convertir en un GNFA?

Answer 1

(Comme il est un problème de devoirs, je suppose que vous voulez juste assez d'aide pour commencer, et non une solution complète travaillé?)

Votre kilométrage peut varier, mais je ne le font pas recommande vraiment d'essayer de convertir un NFA en une expression régulière. Les deux sont théoriquement équivalents, et l'un ou l'autre peut être converti en l'autre algorithmiquement, mais à mon avis, ce n'est pas la manière la plus intuitive de construire l'un ou l'autre.

Au lieu de cela, une approche est de commencer par différentes possibilités qui énumèrent:

• Aucune paire de zéros consécutifs du tout; c'est-à-dire que chaque zéro, sauf à la fin de la chaîne, doit être suivi d'un. Ainsi, la chaîne se compose d'une séquence mixte d'1 et 01, éventuellement suivie d'0:

  (1|01)*(0|ε) 
  

• Exactement une paire de zéros consécutifs, à la fin de la chaîne. Ceci est très similaire à la précédente:

  (1|01)*00 
  

• Exactement une paire de zéros consécutifs, pas à la fin de la chaîne — et, par conséquent, nécessairement suivie d'un. Ceci est également très similaire à la première:

  (1|01)*001(1|01)*(0|ε) 
  

Pour poursuivre cette approche, alors vous étendre ci-dessus pour soutenir deux paires de zéros consécutifs; et enfin, vous fusionnez tous ceux-ci en une seule expression régulière.

Answer 2

contient au maximum deux paires de 0 consécutifs

(1|01)*(00|ε)(1|10)*(00|ε)(1|10)* 

Answer 3

(0 + 1) * 00 (0 + 1) * 00 (0 + 1) * + (0 + 1) * 000 (0+ 1) *