TD2 - Automates et Langages - RICM
Exercice. Encore des automates à construire.
Construire les automates non-déterministes qui reconnaissent
les langages suivants sur l'alphabet {a,b}
- Tous les mots qui contiennent abab
- Tous les mots qui se terminent par abb
ou par aaa.
- Tous les mots qui commencent par abba
ou ont la forme abababab....
Ecrire explicitement leurs relations de
transition.
Exercice. Un automate à déterminiser.
Construire un automate déterministe acceptant le même
langage que l'automate suivant. Dessiner les diagrammes de
transitions.
Q={p,q,r,s}, Sigma={0,1}, q0=p, F={s},
Delta= {p0p,p0q,p1p,q0r,q1r,r0s,s0s,s1s}
Comparez les deux automates - quels sont
les avantages et désavatages des automates déterministes et non-déterministes?
Pour vous entraîner, faites la même manipulation sur les
automates de l'exercice précédent.
Problème théorique. Epsilon-transitions et leur élimination.
Un automate suivant a plusieurs transitions etiquetées par epsilon.
Ce sont les transitions que l'automate peut prendre sans
lire un caractère de l'entrée.

- Trouver les calculs accepteurs de l'automate sur les mots
suivants: aaac, abbcccc
- Décrire (en français) le langage de l'automate
- Construire un automate (non-déterministe) sans epsilon-transitions
acceptant le même langage. (Indication: il faut
modifier la relation de transition et les états finaux
seulement).
- Formuler le théorème sur l'élimination d'epsilon-transitions.
Qu'est-ce qu'il reste à faire pour le démontrer?
TD1 TD3 TD4 TD5 TD7
Retour