Automates à pile

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

- Q est un ensemble fini d’états,

- Σ est un alphabet d’entrée,

- Γ est un alphabet de pile,

- Δ ⊂ ((Q × Σ^{∗} × Γ^{∗}) × (Q × Γ^{∗})) la relation de transition (ensemble fini),

- Z ∈ Γ est le symbole initial de la pile,

- s ∈ Q l’état initial,

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

M est un automate à pile.

exe.: Soit P_{1} = ({s, p, q}, {a, b}, {A, Z}, Δ, Z, s, {q})

avec Δ :\{ \begin{matrix}((s, a, ε), (s, A)) \\ ((s, ε, Z), (q, ε)) \\ ((s, b, A), (p, ε)) \\ ((p, b, A), (p, ε)) \\ ((p, ε, Z), (q, ε))\} \end{matrix}

P_{1} est un automate à pile.

Automates à pile (suite)

def.: Le triplet (q, u, β) ∈ Q × Σ^{∗} × Γ^{∗} est une configuration.

def.: La configuration (q′, w′, α′) est dérivable en une étape de la configuration (q, w, α) par l’automate à pile M (noté (q, w, α) ⊢_{M} (q′, w′, α′)) si w = uw′, u ∈ Σ^{∗}, α = βδ, β, δ ∈ Γ^{∗}, α′ = γδ, γ ∈ Γ^{∗}, et ((q, u, β), (q′, γ)) ∈ Δ.

exe.: (p, baba, AAZ) ⊢_{P_{1}} (p, aba, AZ) par :

- p = q, p = q′, w = baba, w′ = aba, α = AAZ, α′ = AZ,

- u = b, β = A, γ = ε, δ = AZ,

- ((p, b, A), (p, ε)) ∈ Δ,

def.: Une configuration C′ est dérivable en plusieurs étapes de la configuration C par l’automate à pile M (C ⊢_{M}^{∗} C′) si ∃k ≥ 0 et C_{0}, …, C_{k} des configurations telles que

- C = C_{0},

- C′ = C_{k},

- C_{i} ⊢_{M} C_{i+1} , ∀i, 0 ≤ i < k.

Automates à pile (suite)

def.: L’exécution d’un automate à pile M sur un mot w est la suite des configurations (s, w, Z) ⊢_{M} (q_{1}, w_{1}, α_{1}) ⊢_{M} … ⊢_{M} (q_{n}, ε, γ). exe.: (s, aabb, Z) ⊢_{P_{1}}^{∗} (q, ε, Z) :

configurations transitions
(s, aabb, Z) ((s, a, ε), (s, A))
(s, abb, AZ) ((s, a, ε), (s, A))
(s, bb, AAZ) ((s, b, A), (p, ε))
(p, b, AZ)  ((p, b, A), (p, ε))
(p, ε, Z)  ((p, ε, Z), (q, ε))

(q, ε, ε) def.: Un mot est accepté par un automate à pile M si (s, w, Z) ⊢_{M}^{∗} (q, ε, γ) avec q ∈ F. exe.: Le mot aabb est accepté par l’automate à pile P_{1}.

Automates à pile (suite)

def.: Le langage accepté par un automate à pile M est l’ensemble L(M) des mots acceptés par M. exe.: L’automate à pile P_{1} accepte le langage {a^{n}b^{n}/n ≥ 0}. exo.: Décrire un automate à pile qui accepte le langage {ww^{R}}.