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}

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.

Exercice 4. Le dernier automate.

Déterminiser l'automate suivant:

Retour