Caractérisation des langages hors-contexte

Th. Un langage est hors-contexte si et seulement si il est accepté par un automate à pile.

Const.: Grammaire hors-contexte ⇒ automate à pile. Soit la grammaire hors contexte G = (V_{G}, Σ, R_{G}, S_{G}), nous construisons l’automate à pile M = (Q, Σ, Γ, Δ, Z, s, F) tel que L(G) = L(M) de la manière suivante :

- Q = {s, q, r}, Γ = V ∪ {Z}, Z ∉ V,F = {r},

- Δ = \begin{matrix}\{((s, ε, ε), (q, S)), ((q, ε, Z), (r, ε))\}∪ \\ \{((q, ε, A), (q, x))/A → x ∈ R\}∪ \\ \{((q, a, a), (q, ε))/a ∈ Σ\} \end{matrix}