TD2 - Automates et Langages - RICM

Exercice 1. 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 2. Un automate à déterminiser.

Construire un automate déterministe équivalent à (acceptant le même langage que) l'automate suivant. Dessiner les diagrammes de transitions.

Q={p,q,r,s}, S={0,1}, q0=p, F={s}, D= {p0p,p0q,p1p,q0r,q1r,r0s,s0s,s1s}

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 de l'exercice précédent.

Exercice 3. Epsilon-transitions et leur élimination.

Un automate suivant a plusieurs epsilon-transitions etiquetées par e. 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 déterministe équivalent
• Sujet de réfléxion: Comment construire un automate non-déterministe équivalent avec 3 états (Indication: il faut modifier la relation de transition et les états finaux seulement). Formuler le théorème sur l'élimination d'epsilon-transitions (sans déterminisatrion). Qu'est-ce qu'il reste à faire pour le démontrer?

Exercice 4. Le dernier automate.

Déterminiser l'automate suivant:

Retour