Théorie des langages : Td 4 automates finis langage l
Télécharger PDFUniversité Abdelhamid Mehri – Faculté des NTIC – Licence 2 (TD n°4)
Exercice 1
Donner un automate d’états finis qui reconnaît le langage L = {cc*bd, a(ba)*bcc*ab}.
L’automate est défini par A = (VT, Q, q0, δ, F) avec :
- VT = {a, b, c, d} (ensemble des symboles terminaux)
- Q = {q0, q1, q2, q3, q4, q5, q6, q7, q8} (ensemble des états)
- q0 : état initial
- F = {q3} (ensemble des états finaux)
Exercice 2
Construisez l’automate à états finis qui accepte le langage L dont les mots sur VT = {a, b, c, d} ne se terminent que par abc.
L’automate est défini par A = (VT, Q, q0, δ, F) avec :
- VT = {a, b, c, d} (ensemble des symboles terminaux)
- Q = {q0, q1, q2, q3} (ensemble des états)
- q0 : état initial
- F = {q3} (état final)
Table de transition δ :
| a | b | c | d | |
|---|---|---|---|---|
| q0 | {q0, q1} | q0 | q0 | q2 |
| q1 | — | q2 | — | — |
| q2 | — | — | q3 | — |
| q3 | — | — | — | — |
Explications :
- De l’état q0, un arc étiqueté a mène vers q0 et q1.
- De q1, un arc étiqueté b mène vers q2.
- De q2, un arc étiqueté c mène vers q3 (état final).
Exercice 3
Construisez un automate A sur VT = {a, b} qui reconnaît un langage dont les mots ne contiennent jamais la sous-chaîne « bab ».
L’automate est défini par A = (VT, Q, q0, δ, F) avec :
- VT = {a, b} (ensemble des symboles terminaux)
- Q = {q0, q1, q2} (ensemble des états)
- q0 : état initial
- F = {q0, q1, q2} (tous les états sont finaux)
Table de transition δ :
| a | b | |
|---|---|---|
| q0 | q0 | q1 |
| q1 | q2 | q1 |
| q2 | q0 | q1 |
Exercice 4
Construisez un automate A sur VT = {a, b} qui reconnaît le langage L tel que L = {w ∈ {a, b}* / w = anbma ou w = ban ; n, m ≥ 1}.
L’automate est défini par A = (VT, Q, q0, δ, F) avec :
- VT = {a, b} (ensemble des symboles terminaux)
- Q = {q0, q1, q2, q3, q4, q5} (ensemble des états)
- q0 : état initial
- F = {q3, q5} (états finaux)
Table de transition δ :
| a | b | |
|---|---|---|
| q0 | q1 | q4 |
| q1 | q1 | q2 |
| q2 | q3 | q2 |
| q3 | — | — |
| q4 | q4 | q5 |
| q5 | — | — |
FAQ
Qu’est-ce qu’un automate à états finis ?
Un automate à états finis est un modèle mathématique utilisé en informatique théorique pour reconnaître des langages formels. Il se compose d’un ensemble d’états, d’un alphabet, d’une fonction de transition et d’un ensemble d’états finaux.
Comment construire une table de transition ?
La table de transition δ décrit les mouvements possibles entre les états en fonction des symboles de l’alphabet. Chaque ligne représente un état et chaque colonne un symbole. Les cases contiennent les états atteints après lecture du symbole correspondant.
Pourquoi certains états sont-ils finaux ?
Les états finaux marquent la fin d’une reconnaissance réussie d’un mot du langage. Par exemple, dans l’exercice 2, l’état q3 est final car il correspond à la lecture de la sous-chaîne « abc » à la fin du mot.