TD3 - Automates et Langages - RICM
Exercice 1. Calcul des successeurs.
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
- Soient r et s des expressions régulières. Calculer les
expressions suivantes : Ø+r, e+r, Ør,
rØ, er, re.
- Comparer Ø, e avec 0 et 1.
- Quelles sont d'autres
propriétés algébriques des expressions régulières?
- Simplifier Ø*, e*, (e+r)*