Automate fini déterministe

Description informelle d’un AFD

- une tête de lecture qui indique le caractère suivant à lire sur le ruban d’entrée où est placé l’instance du problème ;

- un ensemble d’états finis (état initial et états accepteurs) ;

- une fonction de transition qui indique pour chaque état et chaque symbole lu l’état suivant.

Exécution informelle d’un AFD:

- Départ : état initial et tête de lecture sur le premier caractère du mot d’entrée ;

- A chaque étape : lecture du caractère, application de la fonction de transition, déplacement de la tête de lecture ;

- Arrêt : Le mot est accepté si l’automate est dans un état accepteur.

Description formelle d’un AFD

def.: Soit M = (Q, Σ, δ, s, F)

- Q est un ensemble fini d’états,

- Σ est un alphabet,

- δ : Q × Σ → Q la fonction de transition,

- s ∈ Q l’état initial,

- F ⊆ Q l’ensemble des états accepteurs.

M est un automate fini déterministe.

def.: Le couple (q, w) ∈ Q × Σ^{∗} est une configuration.

def.: La configuration (q′, w′) est dérivable en une étape de la configuration (q, w) par l’AFD M (noté (q, w) ⊢_{M} (q′, w′)) si, par définition, w = σw′, σ ∈ Σ et q′ = δ(q, σ).

Description formelle d’un AFD (suite)

def.: La configuration (q′, w′) est dérivable de la configuration (q, w) par l’AFD M (noté (q, w) ⊢_{M}^{∗} (q′, w′)) si, par définition, il existe k ≥ 0 et des configurations (q_{i}, w_{i}), 0 ≤ i ≤ k telles que

- (q, w) = (q_{0}, w_{0}),

- (q′, w′) = (q_{k}, w_{k}),

- ∀i, 0 ≤ i ≤ k, (q_{i}, w_{i}) ⊢_{M} (q_{i+1} , w_{i+1} ).

def.: L’exécution d’un automate M sur un mot w est la suite des configurations (s, w) ⊢_{M} (q_{1}, w_{1}) ⊢_{M} … ⊢_{M} (q_{n}, ε).

def.: Un mot est accepté par un AFD M si (s, w) ⊢_{M}^{∗} (q, ε) avec q ∈ F.

def.: Le langage accepté par un AFD M est l’ensemble L(M) des mots acceptés par M.

Exemples d’AFD

exe.: Soit l’AFD M suivant : Q = {q_{0}, q_{1}}, Σ = {a, b}, s = q_{0}, F = {q_{1}}, δ définie par :

\begin{matrix}q & q_{0} & q_{0} & q_{1} & q_{1} \\ σ & a & b & a & b \\ δ(q, σ) & q_{0} & q_{1} & q_{0} & q_{1} \end{matrix}

L(M) = {w | w se termine par b}.

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

Automate fini non déterministe

Description informelle d’un AFND Les AFND sont des AFD où l’on permet plusieurs transitions correspondant à la même lettre dans chaque état.

Les ε-AFND sont des AFND où l’on permet des transitions sur ε (i.e. sans avancer la tête de lecture).

(On permet parfois des transitions sur des mots de longueur supérieur à 1.)

Description formelle d’un AFND

def.: Soit M = (Q, Σ, Δ, s, F)

- Q est un ensemble fini d’états,

- Σ est un alphabet,

- Δ ⊂ (Q × Σ × Q) la relation de transition,

- s ∈ Q l’état initial,

- F ⊆ Q l’ensemble des états accepteurs.

M est un automate fini non déterministe.

Les autres définitions sont étendues de façon immédiate.

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

Équivalence d’automates

def.: Deux automates M et M′ sont équivalents si ils acceptent le Mme langage (i.e. L(M) = L(M′)).

Th.: Pour tout AFND il existe un AFD équivalent.

Const.: Soit un AFND M = (Q, Σ, Δ, s, F), nous construisons un AFD M′ = (Q′, Σ′, δ′, s′, F′) équivalent à M de la manière suivante

- Q′ = 2^{Q}, Σ′ = Σ, s′ = {s},

- δ′(\overline{q}, a) = ⋃\{p ∈ Q | ∃q ∈ \overline{q}, (q, a, p) ∈ Δ\},

- F′ = \{\overline{q} ∈ Q′ | \overline{q} ∩ F ≠ ∅\}.

exo.: 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}

Th.: Pour tout ε-AFND il existe un AFND équivalent.