Propriétés de clotures des automates finis

Un langage reconnaissable est un langage pour lequel il existe un automate fini qui reconnait ce langage.

Théorème :

Si \(L\subseteq A^*\) est un langage reconnaissable, alors son complémentaire \(A^*\setminus L\) est aussi reconnaissable.

Union et intersection de langages

Produit cartésien d’AF

Soit \(A_i(A, Q_i, I_i, F_i, \delta_i), i=1,2\) deux AF.
Soit :

\[Q = Q_1 \times Q_2\]
\[I = I_1 \times I_2\]
\[F_{\cup} = \{(q_1, q_2)\in Q \setminus q_1\in F_1 OU q_2\in F_2\}\]
\[F_{\cap} = \{(q_1, q_2)\in Q \setminus q_1\in F_1 ET q_2\in F_2\}\]
\[\delta=\{((p_1, p_2), \alpha, (q_1, q_2))\in Q\times A\times Q \setminus (p_1, \alpha, q_1)\in \delta_1 ET (p_2, \alpha, q_2)\in \delta_2\}\]

Soit \(A_{\cap}=(A,Q,I,F_{\cap},\delta)\) et \(A_{\cup}=(A,Q,O,F_{\cup},\delta)\)

Théorèmes :

L’AF \(A_{\cap}\) reconnait l’intersection des langages reconnus par \(A_1\) et \(A_2\).

Si \(A_1\) et \(A_2\) sont complets, \(A_{\cup}\) reconnait l’union des langages reconnus par \(A_1\) et \(A_2\).

Si \(L_1\) et \(L_2\) sont deux langages reconnaissables alors \(L_1\cap L_2\) et \(L_1\cup L_2\) sont aussi reconnaissable.
La classe de langages reconnaissable est clot par union ou intersection des langages.

Exemple :

\[F_{\cup} = \{(q_3,q_4), (q_3,q_5), (q_3,q_6), (q_1,q_6), (q_2,q_6)\}\] \[F_{\cap} = \{(q_3,q_6)\}\]

AF avec \(\epsilon\)-transitions

C’est un AFM, mais il peuvent avoir des transitions sur le mot vide \(\epsilon\) (\(\epsilon\)-transition).

\(\epsilon\)-cloture

\(clot(q) = p \setminus p\in Q\) tels qu’il existe un chemin étiquetté \(\epsilon\) qui va de l’état \(q\) à \(p\).

Passage entre AF et expressions rationnelles

Théorème de Kleene

On peut convertir de manière algorithmique une expression rationnelle en AF qui reconnait le même langage.
Et inversement, on peut convertir de manière algorithmique un AF en expression rationnelle qui reconnait le même langage.

Expression rationnelle vers AF

Algorithme de Thompson

Input : expression rationnelle
Output : un AF \(\epsilon\)-transition

Les AF construits ont un unique état initial sur lequel n’arrive aucune transition et un unique état final duquel ne part aucune transition.

On suppose qu’on sait faire un AF pour les expressions régulières l1 et l2.

A reconnait l1+l2 :

On créé un nouveau sommet initial qui a des \(\epsilon\)-transition vers les états initiaux de l1 et l2.
On créé des nouvelles \(\epsilon\)-transition des états finaux de l1 et l2 vers un même nouvel état final.

A reconnait l1.l2 :

On créé une \(\epsilon\)-transition qui va de l’état final de l1 vers l’état initial de l2.

A reconnait l1* :

On créé un nouvel état initial qui a une \(\epsilon\)-transition vers l’état initial de l1 et vers un nouvel état final. On rajoute une \(\epsilon\)-transition de l’état final de l1 vers le nouveau état final et l’état initial de l1.

Retour
Cours précédent
Cours suivant