TD sur les Automates finis et les Automates à pile

Igor Stéphan 2 mars 1999

Références

[Wol91] P. Wolper. Introduction à la calculabilité. InterÉditions, 1991.

1 Automates finis

1.1 Automates finis déterministes

Construire un AFD M sur l’alphabet {a, b} qui accepte le langage L(M) = {w | w ne contient pas consécutivement 2 a}.

L’AFD M est défini par :

M = ( \begin{matrix}\{q_{0}, q_{1}, q_{2}\}, \{a, b\}, \\ \{(q_{0}, a, q_{1}), (q_{0}, b, q_{0}), (q_{1}, a, q_{2}), (q_{1}, b, q_{0}), (q_{2}, a, q_{2}), (q_{2}, b, q_{2})\}, \\ q_{0}, \{q_{0}, q_{1}\}) \end{matrix}

Déterminer l’automate fini déterministe M qui accepte le langage des mots sur l’alphabet {a, b} tels que le nombre d’occurrences de b soit divisible par 3.

L’AFD M est défini par :

( \begin{matrix}\{q_{0}, q_{1}, q_{2}\}, \{a, b\}, \\ \{(q_{0}, a, q_{0}), (q_{0}, b, q_{1}), (q_{1}, a, q_{1}), (q_{1}, b, q_{2}), (q_{2}, a, q_{2}), (q_{2}, b, q_{0})\}, \\ q_{0}, \{q_{0}\}) \end{matrix}

Déterminer l’automate fini déterministe M qui accepte le langage des mots sur l’alphabet {a, b} tels qu’ils contiennent exactement un b.

L’AFD M est défini par :

( \begin{matrix}\{q_{0}, q_{1}, q_{2}\}, \{a, b\}, \\ \{(q_{0}, a, q_{0}), (q_{0}, b, q_{1}), (q_{1}, a, q_{1}), (q_{1}, b, q_{2}), (q_{2}, a, q_{2}), (q_{2}, b, q_{2})\}, \\ q_{0}, \{q_{1}\}) \end{matrix}

1.2 Automates finis non-déterministes

Construire un AFND M sur l’alphabet {a, b} qui accepte le langage L(M) = {w | w se termine par ab}.

L’ADNF M est défini par :

( \begin{matrix}\{q_{0}, q_{1}, q_{2}\}, \{a, b\}, \\ \{(q_{0}, a, q_{0}), (q_{0}, b, q_{0}), (q_{0}, a, q_{1}), (q_{1}, b, q_{2}), (q_{1}, a, q_{0}), (q_{2}, a, q_{0}), (q_{2}, b, q_{0})\}, \\ q_{0}, \{q_{2}\}) \end{matrix}

1.3 Des AFD aux AFND

Construire un AFD équivalent à l’AFND suivant :

M = ( \begin{matrix}\{q_{0}, q_{1}\}, \{0, 1\}, \\ δ = \{(q_{0}, 0, q_{0}), (q_{0}, 0, q_{1}), (q_{0}, 1, q_{1}), (q_{1}, 1, q_{0}), (q_{1}, 1, q_{1})\}, \\ q_{0}, \{q_{1}\}). \end{matrix}

L’AFD suivant est équivalent à l’AFND ci-dessus. δ′({q_{0}}, 0) = {q_{0}, q_{1}},

δ′({q_{0}}, 1) = {q_{1}},
δ′({q_{0}, q_{1}}, 0) = {q_{0}, q_{1}},
δ′({q_{0}, q_{1}}, 1) = {q_{0}, q_{1}},
δ′({q_{1}}, 1) = {q_{0}, q_{1}}

donc

({{q_{0}}, {q_{1}}, {q_{0}, q_{1}}}, {0, 1}, δ′, {q_{0}}, {{q_{1}}, {q_{0}, q_{1}}})

Construire un AFD équivalent à l’AFND suivant :

M = ( \begin{matrix}\{q_{0}, q_{1}, q_{2}, q_{3}, q_{4}\}, \{a, b\}, \\ δ = \{ \begin{matrix}(q_{0}, a, q_{1}), (q_{0}, b, q_{3}), \\ (q_{1}, a, q_{3}), (q_{1}, a, q_{2}), \\ (q_{2}, b, q_{1}), \\ (q_{3}, a, q_{1}), (q_{3}, a, q_{3}), (q_{3}, b, q_{4}), \\ (q_{4}, b, q_{3}), (q_{4}, a, q_{1}), (q_{4}, a, q_{2})\}, \end{matrix} \\ q_{0}, \{q_{4}\}). \end{matrix}

L’AFD suivant est équivalent à l’AFND ci-dessus. δ′({q_{0}}, a) = {q_{1}}, δ′({q_{0}}, b) = {q_{3}}, δ′({q_{1}}, a) = {q_{2}, q_{3}}, δ′({q_{3}}, a) = {q_{1}, q_{3}}, δ′({q_{3}}, b) = {q_{4}}, δ′({q_{2}, q_{3}}, a) = {q_{1}, q_{3}}, δ′({q_{2}, q_{3}}, b) = {q_{1}, q_{4}}, δ′({q_{1}, q_{3}}, a) = {q_{1}, q_{2}, q_{3}}, δ′({q_{1}, q_{3}}, b) = {q_{4}}, δ′({q_{4}}, a) = {q_{1}, q_{2}}, δ′({q_{4}}, b) = {q_{3}}, δ′({q_{1}, q_{4}}, a) = {q_{1}, q_{2}, q_{3}}, δ′({q_{1}, q_{4}}, a) = {q_{3}}, δ′({q_{1}, q_{2}, q_{3}}, a) = {q_{1}, q_{2}, q_{3}}, δ′({q_{1}, q_{2}, q_{3}}, b) = {q_{1}, q_{4}}, δ′({q_{1}, q_{2}}, a) = {q_{2}, q_{3}}, δ′({q_{1}, q_{2}}, b) = {q_{1}},

donc ({{q_{0}}, {q_{1}}, {q_{3}}, {q_{4}}, {q_{2}, q_{3}}, {q_{1}, q_{3}}, {q_{1}, q_{4}}, {q_{1}, q_{2}, q_{3}}, {q_{1}, q_{2}}}, {a, b}, δ′, {q_{0}}, {{q_{4}}, {q_{1}, q_{4}}})

2 Automates à pile

Décrire un automate à pile qui accepte le langage {ww^{R}}.

L’automate à pile suivant accepte le langage {ww^{R}}.

( \begin{matrix}\{s, p, q\}, \\ \{a, b\}, \\ \{A, B, Z\}, \\ \{((s, a, ε), (s, A)), ((s, b, ε), (s, B)), ((s, ε, ε), (p, ε)), \\ ((p, a, A), (p, ε)), ((p, b, B), (p, ε)), ((p, ε, Z), (q, ε))\}, \\ Z, \\ s, \\ \{q\}) \end{matrix}