TD7-8 - Automates et Langages - RICM
Lemme de gonflement
Exercice 1. Preuve de non-régularité
Prouver que le langage P de tous les palindromes sur {a,b}
n'est pas régulier (w est un palindrome si w=wR).
Indication:
- supposer le contraire
- prendre un mot w concret assez long dans P
- montrer que la version gonflée de ce mot est dans P (par
"pumping lemma")
- montrer que cette même version gonflée n'est pas un
palindrome
- déduire la contradiction et terminer la preuve
Exercice 2. Le bon grain et l'ivraie
Lesquels des langages suivants sont réguliers? Justifiez
votre réponse.
- les mots sur {a,b} sans trois a consécutifs
- les mots sur {a,b} avec autant de a que de b
- les mots sur {a,b} dont la longueur est impaire
- {axbycz | x+y=z}. Une solution
est disponible.
- les mots sur {a,b} dont la longueur est un nombre premier
- les mots sur {a,b} de longueur 1000000
- les noms de variables d'ADA
- les expressions arithmétiques de ADA
- les programmes syntactiquement correctes en ADA
- les expressions booléennes d'ADA
- les mots sur {0,1,...,9} représentant les nombres
multiples de 5 en système décimal
- même question pour les multiples de 3
Minimisation
Pour minimiser un automate déterministe il faut
- effacer les états inaccessibles
- construire la relation d'équivalence
- trouver ses classes d'équivalence
- construire l'automate minimal dont les états
son les classes d'équivalence qu'on vient de construire
Méthode pratique de construction de la relation d'équivalence:
- On construit un tableau de taille N x N (N est
le nombre d'états de notre automate). Chaque case dans
ce tableau correspond à un couple d' états (p,q). Pour
ne pas avoir deux fois le même couple ((p,q) et (q,p))
ni les couples inutiles (p,p), on garde seulement la
partie triangulaire supérieure du tableau. (Notre but final est de cocher toute les
cases (p,q) pour des états p et q non-équivalents)
- Au début on coche chaque case (p,q) correspondant
à un état final et à un état non-final (c'est
à dire p dans F et q dans Q-F ou à l'envers, p dans Q-F
et q dans F).
- On balaie toutes les cases vides du tableau d'une manière
quelconque en le modifiant de façon suivante : pour
chaque case (p,q) et lettre a, on calcule d(p,a)=p' et d(q,a)=q'. On coche (p,q)
si et seulement si la case (p',q') est déjà cochée.
- On répète le balayage jusqu'au moment quand le
tableau ne se modifie plus.
- La relation d'équivalence se cache dans le
tableau final : deux états p et q sont équivalents
si et seulement si la case (p,q) n'est pas cochée.
Exercice 3. On minimise.
1. Calculer l'automate minimal équivalent à (=acceptant le même
langage que) l'automate suivant:
Q={a,b,c,d,e}, S={0,1}, q0=a,
F={a,c}, d est donné par la table:
|
a
|
b
|
c
|
d
|
e
|
0
|
b
|
e
|
d
|
e
|
e
|
1
|
e
|
c
|
e
|
a
|
e
|
Pourquoi les états a et b ne sont pas équivalents? a et e?
Trouver les calculs de l'automates original et minimal sur 010111
et les comparer.
2. Même question pour Q={a,b,c,d,e,f,g,h}, S={0,1}, q0=a, F=d, d est donné par la table:
|
a
|
b
|
c
|
d
|
e
|
f
|
g
|
h
|
0
|
b
|
a
|
d
|
d
|
d
|
g
|
f
|
g
|
1
|
a
|
c
|
b
|
a
|
f
|
e
|
g
|
d
|
Exercice 4. On déterminise et minimise.
Calculer l'automate minimal équivalent à l'automate suivant:
Q={0,1,2,3,4,5}, S={a,b}, q0=0,
F=4, d est donné par la table:
|
0
|
1
|
2
|
3
|
4
|
5
|
a
|
12345
|
23
|
014
|
0
|
1
|
2
|
b
|
|
4
|
123
|
125
|
|
235
|
Indication: n'oubliez pas de déterminiser d'abord
Quel est le langage accepté?
Retour