Math: Donner une expression régulière à une langue:

Question

Je vais plus loin et j'apprends des expressions régulières et des langues. Je travaillais à travers quelques questions à propos de donner une expression régulière pour représenter une langue spécifiée. La question que j'ai été un peu coincé sur est la suivante:

Venez avec une expression régulière qui exprime le langage suivant . L'alphabet de la langue est {a, b}.

La langue de toutes les chaînes avec deux a consécutifs, mais pas trois consécutifs a. (c'est-à-dire, "aa", "aabaa", "babaa" sont dans la langue, tandis que "abab", "aaaab" ne l'est pas).

Ma réponse à cette jusqu'à présent est:

(b*(e+a+aa)bb*)* (aa) (bb*(e+a+aa)b*)* 

où « e » est la chaîne vide « et '+ » fonctionne essentiellement comme un « ou ».

Je suppose que je me demande si ma réponse est correcte (je crois que c'est le cas), et si cela peut être simplifié?

Merci les gars.

Answer 1

Je crois que l'expression régulière est correcte. Il s'assure qu'un aa existe dans la chaîne et vérifie que aaa ne peut pas exister. Je dirais que ce qui suit est plus simple que pour être plus simple (plus simple étant ici subjective),:

(b + ab + aab)* aa (b + ba + baa)* 

Notez que vous pouvez réellement tirer ci-dessus de l'expression régulière que vous avez. En prenant seulement la partie avant la aa dans votre expression régulière, nous avons:

(b*(e+a+aa)bb*)* 
= (b*bb* + b*abb* + b*aabb*)* 
= (b + ab + aab)* 

Cette dernière étape est un peu d'un saut, mais il faut remarqué que tous ces b* « s sont licenciés en raison de la * sur l'expression entière, et un b existant à l'intérieur des parenthèses.

Answer 2

Je pense que ce regex correspond à votre langue ainsi:

^((ab|b)*aa(ba|b)*)*$