TD5 - Automates et Langages - RICM

Traductions

Exercice 1. Automates >>> Expressions régulières

Ecrire les expressions régulières pour les langages des automates suivants:

Conseils : pour simplifier les calculs on peut mettre l'équation pour l'état initial après toutes les autres équations et arrêter l'algorithme dès que cette dernière équation est résolue.

Propriétés des langages réguliers

Exercice 2. Opérations sur les langagages et les automates.

Soient L = ab(a+b)* et M= (a+b)*ba - deux langages sur {a,b}. Pour commencer construisez les automates qui reconnaissent L et M.

Trouvez les expressions et/ou les automates pour les langages suivants:

• L U M, LM, L* (facile et vu en cours)
• ¬L (complément), ¬M
• L^M (intersection). Indication : on peut passer aux compléments

Exercice 3. Le miroir.

On utilise la notation w^R pour le mot w "renversé". Par exemple, papa^R=apap. Cette opération peut être étendu sur les langages - par exemple ((ab)*)^R=(ba)*

• Trouvez l'expression régulière pour ((ab)*(a+bbba)+a*b*)^R
• Trouvez les automates pour les langages de l'exercice 1 renversés
• Prouvez que si L est régulier, alors L^R est aussi régulier (les langages réguliers sont fermés par rapport au renversement)

TD1 TD2 TD3 TD4 TD7

Retour