Donne une expression rationnelle sur Σ = {a, b} ...?

Question

La question demande de donner une expression régulière sur Σ = {a, b} dans une représentation formelle (non java) qui génère les langues suivantes:

1. L1 = {x | x contient la sous-chaîne ABAB}
2. L2 = {x | x a une longueur impair}
3. L3 = {x | x ne se termine pas ab}

Je n'ai aucune idée comment écrire une expression régulière. Quelles seraient les réponses et si vous pouviez expliquer pourquoi je serais extrêmement reconnaissant.

Answer 1

Il existe de nombreuses notations pour les expressions régulières qui diffèrent dans les détails. Vos solutions ressemblera à quelque chose comme:

1. Σ * · ABAB · Σ *
2. a · {aa, bb, ab, ba} * \ tasse b · {aa, bb, ab, ba} *
3. Σ * · {bb, a} cup \ {b, \ lambda}

où cup \ est défini union/OU et \ lambda est la chaîne vide.