Théorie des langages : Cours automates avec epsilon transitions
Télécharger PDFAutomates avec Epsilon-Transitions
Définition
Un automate avec epsilon-transition (e-NFA) est défini par un quintuplet A = (Q, Σ, δ, q₀, F), où :
- Q est l'ensemble des états,
- Σ est l'alphabet de l'automate,
- q₀ est l'état initial,
- F est l'ensemble des états finaux,
- δ : Q × (Σ ∪ {ε}) → 𝒫(Q) est la fonction de transition, avec ε représentant une transition epsilon (sans consommation de symbole).
Exemples
Exemple 1 : Un e-NFA qui accepte les nombres décimaux comme 2.15, .125, +1.4, -0.501, etc.
Pour accepter un nombre tel que "+5.", on ajoute l'état q₄ avec les transitions suivantes :
- q₀ → ε → q₁ ou q₀ → +, - → q₁
- q₁ → 0, 1, ..., 9 → q₂
- q₂ → . → q₃
- q₃ → 0, 1, ..., 9 → q₄
- q₄ → ε → q₅
- q₅ est un état final.
Exemple 2 : Un autre exemple d'un e-NFA défini sur l'alphabet Σ = {a, ..., z}.
Les transitions incluent des transitions epsilon, comme q₀ → ε → q₁ ou q₁ → ε → q₂.
Transformation des automates avec epsilon-transitions en automates déterministes
Pour transformer un e-NFA en un DFA, on utilise la fonction e-fermeture (ECLOSE), définie comme suit :
- 1. Si s ∈ Q, alors s ∈ ECLOSE(s).
- 2. Si s₁ ∈ δ(s, ε), alors s₁ ∈ ECLOSE(s).
- 3. Si s₁ ∈ ECLOSE(s) et s₂ ∈ ECLOSE(s₁), alors s₂ ∈ ECLOSE(s).
On peut étendre cette définition à un sous-ensemble d'états :
ECLOSE(S' ⊆ Q) = ∪s' ∈ S' ECLOSE(s').
La fonction ECLOSE(s) regroupe tous les états accessibles depuis s via des chemins constitués uniquement de transitions epsilon.
Exemple de calcul de la fonction ECLOSE
Pour un automate donné :
- ECLOSE(1) = {1, 2, 3, 4, 6}.
- ECLOSE({3, 5}) = ECLOSE(3) ∪ ECLOSE(5) = {3, 6} ∪ {5, 7} = {3, 5, 6, 7}.
Exercice : Construction d'un e-NFA
Construire un automate avec ε-transitions reconnaissant le langage régulier a*b*c*.
Calculer la fonction ECLOSE pour chaque état de cet automate.
Exemple de transformation d'un e-NFA en un DFA
Soit AE = (QE, ΣE, δE, qE₀, FE) un automate non-déterministe avec ε-transitions (e-NFA). Il existe un automate déterministe AD = (QD, ΣD, δD, qD₀, FD) tel que L(AE) = L(AD).
- QD ⊆ ECLOSE(𝒫(QE)).
- Tous les éléments de ECLOSE(𝒫(ΣE)) sont accessibles depuis l'état initial de QD.
- ΣD = ΣE.
- δD(SD ∈ QD, a ∈ ΣD) = ECLOSE(∪sE ∈ SD δE(sE, a))
- qD₀ = ECLOSE(qE₀).
- FD = {S ∈ QD | (S ∩ FE) ≠ ∅}.
Pour calculer δD(S, a) :
- Soit S = {p₁, p₂, ..., pk}.
- Calculer δE(pi, a) pour chaque pi et obtenir l'ensemble des états résultants {r₁, r₂, ..., rm}.
- δD(S, a) = ECLOSE({r₁, r₂, ..., rm}).
Exemple concret : Elimination des ε-transitions
Pour un automate reconnaissant des nombres décimaux avec les états suivants :
- q₀ → ε → q₁
- q₀ → +, - → q₁
- q₁ → 0, 1, ..., 9 → q₂
- q₂ → . → q₃
- q₃ → 0, 1, ..., 9 → q₄
- q₄ → ε → q₅
- q₅ est un état final.
Les états et transitions du DFA sont construits comme suit :
- qD₀ = ECLOSE(q₀) = {q₀, q₁}.
- δD({q₀, q₁}, +) = ECLOSE(δE(q₀, +) ∪ δE(q₁, +)) = ECLOSE({q₁} ∪ ∅) = ECLOSE(q₁) = {q₁}.
- δD({q₀, q₁}, 0) = ECLOSE(δE(q₀, 0) ∪ δE(q₁, 0)) = ECLOSE(∅ ∪ {q₁, q₄}) = ECLOSE({q₁, q₄}) = {q₁, q₄}.
- δD({q₀, q₁}, .) = ECLOSE(δE(q₀, .) ∪ δE(q₁, .)) = ECLOSE(∅ ∪ {q₂}) = {q₂}.
- δD({q₁, q₄}, 0) = ECLOSE(δE(q₁, 0) ∪ δE(q₄, 0)) = ECLOSE({q₁, q₄} ∪ ∅) = {q₁, q₄}.
- δD({q₁, q₄}, .) = ECLOSE(δE(q₁, .) ∪ δE(q₄, .)) = ECLOSE({q₂} ∪ {q₃}) = ECLOSE(q₂) ∪ ECLOSE(q₃) = {q₂} ∪ {q₃, q₅} = {q₂, q₃, q₅}.
- δD({q₂, q₃, q₅}, 0) = ECLOSE(δE(q₂, 0) ∪ δE(q₃, 0) ∪ δE(q₅, 0)) = ECLOSE({q₃} ∪ {q₃} ∪ ∅) = ECLOSE(q₃) = {q₃, q₅}.
- δD({q₃, q₅}, 0) = ECLOSE(δE(q₃, 0) ∪ δE(q₅, 0)) = ECLOSE({q₃} ∪ ∅) = ECLOSE(q₃) = {q₃, q₅}.
FAQ
1. Qu'est-ce qu'une transition epsilon dans un automate ?
Une transition epsilon (ε-transition) est une transition qui permet de passer d'un état à un autre sans consommer de symbole de l'alphabet. Elle est utilisée pour modéliser des actions internes ou des conditions implicites dans l'automate.
2. Comment calculer la fonction ECLOSE pour un état donné ?
La fonction ECLOSE pour un état s est calculée en incluant tous les états accessibles depuis s via des transitions epsilon, y compris les états atteints par des chaînes de transitions epsilon.
3. Pourquoi transformer un e-NFA en un DFA ?
Transformer un automate non-déterministe avec ε-transitions en un automate déterministe permet de simplifier l'analyse et la reconnaissance des langages, car un DFA offre une unique transition pour chaque état et symbole, facilitant ainsi les algorithmes de traitement.