TD3 - Automates et Langages - RICM

Exercice 1. Calcul des successeurs.

Pour l'automate suivant:

calculer les successeurs

E(p), E(q), E({p,s}), S(p,a);

Succ(p,e), Succ(p,a), Succ(p,ab), Succ(p, aba). Est-ce que aba est accepté?

Traductions

Exercice 2. Français >>> Expressions régulières

Écrire les expressions régulières sur {a,b} dénotant les langages suivants:

• tous les mots de longueur 2
• tous les mots de longueur paire
• tous les mots contenant a
• tous les mos contenant un nombre impair de b
• tous les mots ne contenant pas plus que deux a consécutifs
• tous les mots ne contenant pas aba

Construire aussi des automates finis (nondeterministes, deterministes ou même ayant des e-transitions) pour ces langages.

Exercice 3. Expressions régulières >>> Français

Décrire en français les langages dénotés par les expressions régulières suivantes:

• 0*(10*10*10*)*
• (1+01+001)*(e+0+00)
• (11+0)*(00+1)*

Construire aussi des automates finis (nondeterministes, deterministes ou même ayant des e-transitions) pour ces langages. On peut entrevoir une méthode de transformer n'importe quelle expression régulière en automate fini ?
 

Un peu d'algèbre

Exercice 4. Jouer avec les expressions régulières

1. Soient r et s des expressions régulières. Calculer les expressions suivantes : Ø+r, e+r, Ør, rØ, er, re.
2. Comparer Ø, e avec 0 et 1.
3. Quelles sont d'autres propriétés algébriques des expressions régulières?
4. Simplifier Ø*, e*, (e+r)*