Eliminer les e-transitions
dans l'automate suivant et déterminiser le résultat :
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
Calculer les expressions suivantes : Ø+r,
e+r,
Ør,
er.
Prouver les égalités suivantes (ou r,s,t
sont
des expressions régulières) :
r+s = s+r
(r+s)+t = r+(s+t)
(rs)t = r(st)
r(s+t) = rs+rt
Ø*
=
e
(r*)*=r*
(e+r)*
= r*
(r*s*)* = (r+s)*
et aussi l'implication : rs = st
=> r*s = st*
Quelle égalité est incorrecte parmi les suivantes ?
