Eléments d’ informatique théorique Série 3

Exercice 3.1 Construire un automate déterministe équivalent à l’automate:

q_{0}  q_{1}  q_{3} ϵ ϵ a  b  c ϵ  q_{2}

Définition 3.1 Automate minimal

Un AF déterministe M =< Q, Σ, δ, q_{0}, F > est minimal si et seulement si pour tout AF déterministe M′ =< Q′, Σ, δ′, q′_{0}, F′ > on a L(M) = L(M′) implique |Q| ≤ |Q′|.]

Théorême 3.1 Unicité d’automate minimal

Soit M l’ensemble de tous les automates déterministes M =< Q, Σ, δ, q_{0}, F > qui reconnaîssent le même langage L ⊆ Σ^{∗}. Soit M′ =< Q′, Σ′, δ′, q′_{0}, F′ > un automate déterministe minimal dans M. Alors M′ est unique à isomorphisme près (renommage des états).

Définition 3.2 Algorithme de construction d’un automate minimal

1. Eliminer les états inutiles. Un état est inutile s’il n’y a pas de mot m tel que δ^{∗}(q_{0}, m) = q. L’état q est aussi inutile s’il n’y a pas de mot n tel que δ^{∗}(q, n) ∈ F.

2. Trouver les classes d’équivalence d’états selon la relation R suivante:

la relation R(q, q′) est vraie si et seulement si pour tout mot m ∈ Σ^{∗}

• soit δ^{∗}(q, m) ∈ F et δ^{∗}(q′, m) ∈ F

• soit δ^{∗}(q, m) ∉ F et δ^{∗}(q′, m) ∉ F

Il suffit en fait de ne considérer que les mots m avec |m| ≤ |Q|.

3. Définir: Q′ = {[q]} (c.à.d les classes d’équivalence trouvées),
q′_{0} = [q_{0}],
δ′([q], a) = [δ(q, a)],
F′ = {[q] | q ∈ F } et Σ′ = Σ.

Exercice 3.2 Minimaliser l’automate :

q_{0}  q_{2} a  b  a b b a  b b  b  a q_{1} q_{3}  q_{4}  q_{5} q_{6}  q_{7} a  b a  a a,b  b

Exercice 3.3 Soient L_{1} et L_{2} les langages décidés par M_{1} et M_{2} respectivement. Construire les automates acceptant L_{1}L_{2}, L_{1} ∪ L_{2}, L̄_{1}, L̄_{2} et L_{1} ∩ L_{2}.

q_{0_{1}}  a,b a M_{1}  q_{1_{1}}  a  a b b M_{2}  q_{0_{2}}  q_{1_{2}} q_{2_{2}}