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