Cours 5 : Automates à pile

Définition

Syntaxe

Automate à pile :

$𝒜 ≝ ⟨Q, 𝛴, 𝛤, 𝛿, q_0, z_0, F⟩$ où

  • $Q$ est un ensemble fini d’états
  • $𝛴$ alphabet fini d’entrée
  • $𝛤$ alphabet de pile
  • $𝛿 ⊆ Q × 𝛤 × (𝛴∪ \lbrace 𝜀 \rbrace) × Q × 𝛤^\ast$ finie
  • $q_0∈Q$
  • $z_0 ∈𝛤$ OU $z_0 ∈𝛤^+$
  • $F⊆Q$
  digraph {
    rankdir=LR;
    q_1[shape="doublecircle"];
    ⊥ -> q_0;
    q_0 -> q_0[label="a, A/AA | a, ⊥/⊥A"];
    q_0 -> q_1[label="𝜀, A/A | 𝜀, ⊥/⊥"];
    q_1 -> q_1[label="b, A/𝜀"];
  }

Sémantique opérationnelle

Système de transitions infini sur l’ensemble des configurations $Q×𝛤^\ast$

  • configuration initiale : $q_0, z_0$

  • Transitions : $q, 𝛾z ⟶^a_𝒜 q’, 𝛾𝛾’$ si $(q, z, a, q’, 𝛾’)∈𝛿$

  • Le langage est

    \[L(𝒜) ≝ \lbrace w∈𝛴^\ast \mid ∃ q_f∈ F, 𝛾∈𝛤^\ast; q_0, z_0 ⟶^w_𝒜 q_f, 𝛾\rbrace\]

Exs :

\[\begin{align*} q_0, \bot & ⟶^a q_0, \bot A \\ & ⟶^a q_0, \bot AA \\ & ⟶^𝜀 q_1, \bot \bot AA \\ & ⟶^b q_1, \bot A \\ & ⟶^b q_1, \bot \\ \end{align*}\] \[L(𝒜) ≝ \lbrace a^n b^m \mid n≥ m ≥0 \rbrace\]

Palindromes pairs :

où $x ∈ \lbrace a, b, \bot \rbrace$

  digraph {
    rankdir=LR;
    q_2[shape="doublecircle"];
    ⊥ -> q_0;
    q_0 -> q_0[label="a, x/xA | b, x/xB"];
    q_0 -> q_1[label="𝜀, x/x"];
    q_1 -> q_1[label="b, B/𝜀 | a, A/𝜀"];
    q_1 -> q_2[label="𝜀, ⊥/𝜀"];
  }

Mots bien parenthésés (mots de Dyck) :

  • $a$ : parenthèse ouvrante
  • $b$ : parenthèse fermante

$𝛤 = \lbrace \bot, 1 \rbrace$

  digraph {
    rankdir=LR;
    q_1[shape="doublecircle"];
    ⊥ -> q_0;
    q_0 -> q_0[label="a, x/x1 | b, 1/𝜀"];
    q_0 -> q_1[label="𝜀, ⊥/𝜀"];
  }

NB : Avec la transition $𝜀, ⊥/𝜀$, on vide la définitivement la pile ⟶ on ne peut plus faire de transition dès lors.

Lemme fondamental

Lemme fondamental :

$q, 𝛾𝛾_1 ⟶^w_𝒜 q’’, 𝜀$ en $n$ étapes

ssi

$q, 𝛾_1 ⟶^{w_1}_𝒜 q’, 𝜀$ en $n_1$ étapes

ET

$q, 𝛾 ⟶^{w_2}_𝒜 q’, 𝜀$ en $n_2$ étapes

Preuve

⟸ :

On observe que si $q, 𝛾_1 ⟶^{w_1}_𝒜 q’, 𝜀$ en $n_1$ étapes alors $∀𝛾, q, 𝛾𝛾_1 ⟶^{w_1}_𝒜 q’, 𝛾$ en $n_1$ étapes, puis $q’, 𝛾 ⟶^{w_2}_𝒜 q’’, 𝜀$ en $n_2$ étapes. Le résultat s’ensuit.

⟹ :

Si

\[q, 𝛾 𝛾_1 ⟶^{a_1}_𝒜 q_1, 𝛾𝛾_2 ⟶^{a_2}_𝒜 q_2, 𝛾𝛾_3 \\ ⋯ ⟶^{a_{n_1}}_𝒜 q_{n_1}, 𝛾𝛾_{n_1+1}\]

$∀1≤i≤n, 𝛾_i≠𝜀$

alors

\[q, 𝛾_1 ⟶^{a_1}_𝒜 q_1, 𝛾_2 ⟶^{a_2}_𝒜 q_2, 𝛾_3 \\ ⋯ ⟶^{a_{n_1}}_𝒜 q_{n_1}, 𝛾_{n_1+1}\]

Donc si on prend le calcul où $𝛾_{n_1+1}=𝜀$, $a_1 ⋯ a_{n_1} = w_1$,

$q, 𝛾_1 ⟶^{w_1}_𝒜 q’, 𝜀$ en $n_1$ étapes, puis $q’, 𝛾 ⟶^{w_2}_𝒜 q’’, 𝜀$ en $n_2$ étapes

Acceptance par pile vide

\[N(𝒜) ≝ \lbrace w ∈ 𝛴^\ast \mid ∃q∈Q, q_0 z_0 ⟶^w_𝒜 q, 𝜀\rbrace\]

Prop : Soit $L⊆𝛴^\ast$

\[∃𝒜; L = L(𝒜) ⟺ ∃𝒜'; L = N(𝒜')\]

Preuve :

⟹ :

\[𝒜 ≝ (Q, 𝛴, 𝛤, 𝛿, q_0, z_0, F)\]

On construit

\[𝒜' ≝ (Q', 𝛴', 𝛤', 𝛿', q_0', z_0')\]

en rajoutant un nouveau symbole de fond de pile $\bot$, et des transitions partant des anciens états finals vers un nouvel état $q_f$ qui vide la pile.

On pose :

  • $Q’ ≝ Q \sqcup \lbrace q_f \rbrace$
  • $𝛤’ ≝ 𝛤 \sqcup \lbrace \bot \rbrace$
  • $q’_0 = q_0$
  • $z’_0 =z_0$
  • $𝛿’ ≝ 𝛿 ∪ \lbrace (q,z, 𝜀, q_f, 𝜀) \mid q∈F \text{ ou } q=q_f, z∈𝛤’ \rbrace$
  digraph {
    rankdir=LR;
    subgraph cluster_0 {
      label="𝒜'"
    subgraph cluster_1 {
      label="𝒜"
        q_1[shape=doublecircle, style=dashed]; q_2[shape="doublecircle", style=dashed]; q_3[shape="doublecircle", style=dashed]; ⋯;
    }
    ⊥z_0; q_f;
  }
    ⊥z_0 -> ⋯;
    ⋯ -> {q_1, q_2, q_3};
    q_1 ->q_f[label="𝜀, z/𝜀"];
    q_2 ->q_f[label="𝜀, z/𝜀"];
    q_3 ->q_f[label="𝜀, z/𝜀"];
    q_f -> q_f[label="𝜀, z/𝜀"]
  }

$L(𝒜)⊆N(𝒜’)$

clair

$N(𝒜’) ⊆ L(𝒜)$

Si $q_0, \bot z_0 ⟶^w_{𝒜’} q, 𝜀$ alors $q_0, \bot z_0 ⟶^{w_1}{𝒜’} q_f, 𝛾 ⟶^{w_2}{𝒜’} q_f, 𝜀$

Pour $w=w_1 w_2$ et $q_f$ la première apparition de $q_f$ dans l’exécution : le seul moyen de dépiler $\bot$ est de passer par $q_f$ en $q_f, w_2 = 𝜀$ donc $w_1 = w$ et la première fois où on arrive en $q_f$, la pile vaut soit $𝜀$, soit $\bot 𝛾$.

⟸ :

\[{\cal A}' ≝ ⟨Q \sqcup \lbrace q_f \rbrace, 𝛴, 𝛤 \sqcup \lbrace \bot \rbrace, 𝛿', q_0, \bot z_0, \lbrace q_f \rbrace ⟩\]

où

\[𝛿' ≝ 𝛿 ∪ \lbrace (q, \bot, 𝜀, q_f, 𝜀) \mid q∈F \rbrace\]

On rajoute un nouveau fond de pile $\bot$, et à chaque fois que la pile est “vide” (pour notre nouveau fond), on ajoute des transitions de la forme $q, \bot ⟶^𝜀 q_f, 𝜀$

  digraph {
    rankdir=LR;
    subgraph cluster_0 {
      label="𝒜'"
    subgraph cluster_1 {
      label="𝒜"
        q_1[style=dashed]; q_2[style=dashed]; q_3[style=dashed]; ⋯;
    }
    ⊥z_0;q_f[shape="doublecircle"];
  }
    q_f[shape="doublecircle"];
    ⊥z_0 -> ⋯;
    ⋯ -> {q_1, q_2, q_3};
    q_1 ->q_f[label="𝜀, ⊥/𝜀"];
    q_2 ->q_f[label="𝜀, ⊥/𝜀"];
    q_3 ->q_f[label="𝜀, ⊥/𝜀"];
  }

Th : Si $L = L(G)$ est algébrique, alors on peut construire $𝒜$ un automate à pile tq $L = N(𝒜)$.

Preuve :

Ce qu’on met dans la pile, ce sont des morceaux de dérivation gauche de notre grammaire.

  digraph {
    rankdir=TB;
    ⋯1[label="⋯"];
    ⋯2[label="⋯"];
    ⋯3[label="⋯"];
    subgraph cluster_1 {
      label = "Arbre de dérivation";
      A;⋯1; B; ⋯2; C; ⋯3;
    }
    S -> {A, B, C};
    A -> ⋯1;
    B -> ⋯2;
    C -> ⋯3;
    ⋯1 -> w;
    ⋯2 -> w;
    ⋯3 -> w;
  }

Soit $G = ⟨N, 𝛴, P, S⟩$

On construit

\[𝒜 ≝ ⟨ \lbrace q \rbrace, 𝛴, N∪𝛴, 𝛿, q, S ⟩\]

avec

\[𝛿 ≝ \lbrace (q, A, 𝜀, q, \underbrace{𝛼^R}_{\text{ reverse : le mot à l'envers}}) \mid A ⟶ 𝛼 ∈ P\rbrace \quad \, \text{(règle guess)}\\ ∪ \lbrace (q, a, a, q, 𝜀) \mid a∈𝛴 \rbrace \quad \text{(règle check)}\]

Invariant :

$∀u∈𝛴^\ast, A, B∈N, 𝛾∈(N∪𝛴)^\ast$,

\[B ⟹_{lm}^\ast u A 𝛾 \, \, \text{ ssi } \, \, q, B ⟶^u_𝒜 q, 𝛾^R A\]

  • Cas de base : $B = u A 𝛾$, i.e $B=A ∧ u=𝛾=𝜀$

  • Étape d’induction :

Si

\[B ⟹_{lm}^n u A 𝛾 ⟹_{lm}u \underbrace{𝛼}_{=u'A'𝛾'} 𝛾\]

par HR :

\[\begin{align*} q, B & ⟶^u_𝒜 q, 𝛾^R A &&\text{(guess) } n \text{ fois}\\ q, 𝛾^R A & ⟶^u_𝒜 q, 𝛾^R 𝛾'^R A' u'^R &&\text{(guess) } 1 \text{ fois} \\ q, 𝛾^R 𝛾'^R A' u'^R & ⟶^{u'}_𝒜 q, 𝛾^R 𝛾'^R A' &&\text{(check) } \vert u' \vert \text{ fois} \\ \end{align*}\]

Réciproquement :

Si $q, B ⟶^u_𝒜 q, 𝛾^RA ⟶^𝜀_𝒜 q, 𝛾^R𝛼^R$

où $𝛼 = u’A’𝛾’$ et $q, 𝛾^R 𝛾’^R A’ u’^R ⟶^{u’}_𝒜 q, 𝛾^R 𝛾’^R A’$

Par HR,

\[B ⟹_{lm}^n uA𝛾\]

puis

\[A ⟶ 𝛼\]

donc

\[uA𝛾 ⟹_{lm} uu'A'𝛾'𝛾\]

Par l’invariant :

\[S⟹_{lm}^\ast w \quad \text{ ssi } \quad q, S ⟶^w_𝒜 q, 𝜀\]

Forme normale de GREIBACH (GNF)

Une grammaire est sous GNF :

si $∀A⟶𝛼∈P, 𝛼∈𝛴N^\ast$

Th (GREIBACH) :

Si $G$ est une grammaire algébrique, alors on peut construire $G’$ en GNF tq :

\[L(G)\backslash \lbrace 𝜀\rbrace = L(G')\]

Corollaire : Si $L=L(G)$, $𝒜$ simple (un seul état), en temps réel (pas d’$𝜀$-transition) tq $L\backslash \lbrace 𝜀\rbrace = L(A)$

En effet, les règles guess de la construction précédente deviennent :

  • $q, A ⟶𝜀 q, 𝛽^R,a$ où $A⟶a𝛽 ∈P$

puis

  • $q, 𝛽^Ra ⟶^a q, 𝛽^R$

On les remplace par

\[𝛿 = \lbrace (q, A, a, a, 𝛽^R) \mid A ⟶ a𝛽 ∈P \rbrace\]

Th : Soit $𝒜$ un automate à pile. On peut construire une grammaire algébrique $G$ tq $N(𝒜) = L(G)$ de taille $\vert G \vert ∈ O(\vert 𝒜\vert Q^{M-1})$ où $M$ majore les $m$ (dans la définition de $P$)

NB : $\vert 𝒜 \vert$ est la somme des $m+1$, pour $m$ intervenant dans la définition de $P$.

$G = (N, 𝛴, P, S)$

où

\[N≝ \lbrace (q, z, q') ∈ Q × 𝛤 × Q \rbrace \sqcup \lbrace S \rbrace\]

Invariant :

\[L_G(q, z, q') ≝ \lbrace w∈𝛴^\ast \mid q,z⟶^w_𝒜 q', 𝜀 \rbrace\]

On a

\[N(𝒜) = \bigcup_{q∈Q} L(q_0, z_0, q)\] \[P≝ \lbrace S ⟶ (q_0, z_0, q) \mid q∈Q\rbrace \\ ∪ \lbrace (q,z,q')⟶ a(q_1,z_1,q_2) ⋯ (q_m, z_m, q') \mid (q, z, a, q_1, z_m, ⋯, z_1)∈𝛿, q_2, ⋯ , q_m∈Q \rbrace\] \[L(q, z, q') = \bigcup\limits_{\substack{(q, z, a, q_1, z_m, ⋯, z_1)∈𝛿 \\ q_2,⋯, q_m∈Q}} \lbrace a \rbrace \cdot L(q_1, z_1, q_2) ⋯ L(q_m, z_m, q_2)\]

car :

Si

\[q, z⟶^a_𝒜 q_1, z_m ⋯ z_1 ⟶^w_𝒜 q', 𝜀\]

Par le lemme fondamental, on a l’existence de

$q_2, ⋯, q_m, q_{m+1} = q’$ tq

  • $q_i, z_i ⟶^{w’i}_𝒜 q{i+1}, 𝜀$
  • et $w = w_1 ⋯ w_m$

Leave a comment