Déterminisation d’automates

Objectif : À partir d’un automate fini non-déterministe (AFN) A, construire un automate fini déterministe (AFD) B tels que L(A) = L(B).

Ensemble de sous-ensembles :
Q un ensemble fini, |Q| = n (Q a n éléments)
\(2^Q\) l’ensemble des sous-ensembles de Q.
\(Q = \{Q_1, Q_2, …, Q_n\}\)
\(2^Q = \{\emptyset, \{Q_1\}, \{Q_2\}, …, \{Q_n\}, \{Q_1, Q_2\}, \{Q_1, Q_3\}, …, \{Q_1, Q_n\}, …, \{Q_1, Q_2, …, Q_n\}\}\)
\(|2^Q| = \binom{n}{0} + \binom{n}{1} + \binom{n}{2} + … + \binom{n}{n} = 2^n\)

Méthode de sous-ensembles

Soit AA (A, Q, I, F, \(\delta\)) un AFN.
On construit l’automate BB tels que :

L’ensemble d’états est \(2^Q\)
L’unique état initial est \(\{I\} \in 2^Q\)
Un état \(P \in 2^Q\) est état final de BB si \(P \cap F \neq \emptyset\)
La fonction de transition de BB est donnée par \(\delta_{BB}(P, a) = \bigcup_{p\in P}\delta_{AA}(p, a), \forall P\in 2^Q, \forall a\in A\)

Proposition :
L’automate fini B construit ainsi est un automate fini déterministe complet et L(A) = L(B)

Exemple :
Q = {p, q, r}
I = {p}
F = {r}

\(Q_B = 2^Q = \{\{\emptyset\}, \{p\}, \{q\}, \{r\}, \{p, q\}, \{p, r\}, \{q, r\}, \{p, q, r\}\}\)

B a donc 8 états.

Tableau des transition de A :

\(\delta_A\)	p	q	r
a	{p,q}	\(\emptyset\)	{r}
b	{p}	{r}	{r}

Liste des transitions de B :

\(\delta_B(\{p\}, a) = \delta_A(p, a) = \{p, q\}\)

\(\delta_B(\{p\}, b) = \delta_A(p, b) = \{p\}\)

\(\delta_B(\{q\}, a) = \emptyset\)

\(\delta_B(\{q\}, b) = \{r\}\)

\(\delta_B(\{r\}, a) = \{r\}\)

\(\delta_B(\{r\}, b) = \{r\}\)

\(\delta_B(\{p, q\}, a) = \delta_A(p, a)\cup\delta_A(q, a) = \{p, q\}\cup\emptyset = \{p, q\}\)

\(\delta_B(\{p, q\}, b) = \{p, r\}\)

\(\delta_B(\{p, r\}, a) = \{p, q, r\}\)

\(\delta_B(\{p, r\}, b) = \{p, r\}\)

\(\delta_B(\{q, r\}, a) = \{r\}\)

\(\delta_B(\{q, r\}, b) = \{r\}\)

\(\delta_B(\{p, q, r\}, a) = \{p, q, r\}\)

\(\delta_B(\{p, q, r\}, b) = \{p, r\}\)

\(\delta_B(\emptyset, a) = \emptyset\)

\(\delta_B(\emptyset, b) = \emptyset\)

\(I_B = \{I\} = \{p\}\)

\(F_B = \{\{r\}, \{p,r\}, \{q,r\}, \{p,q,r\}\}\)

La partie de droite (les sommets \(\emptyset\), {q}, {r} et {q,r}) n’est pas accessible. Il est possible de l’enlever pour simplifier le graphe.

Retour
Cours précédent
Cours suivant