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. Calcul des successeurs.

On considère l'automate non-déterministe suivant:

Q={p,q,r,s,t}, Sigma={a,b}, q0=p, F={r,t}, Delta= {pap,paq,pbp,pbs,qar,sbt,rar,rbr,tat,tbt}

Calculer les successeurs suivants:

delta(p,epsilon),delta(p,a); delta(p,ab); delta(p,aba); delta(p,abaa)
delta({r,s}, epsilon); delta({r,s}, b); delta({r,s}, ba)

Exercice. Un automate à déterminiser.

Construire un automate déterministe acceptant le même langage que l'automate de l'exercice précédent. Dessiner les diagrammes de transitions des deux automates.

Comparez les deux automates - quels sont les avantages et désavantages des automates déterministes et non-déterministes?

Pour vous entraîner, faites la même manipulation sur les automates du premier exercice.

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