DM : Automates à pile déterministes

DM de Langages Formels

Younesse Kaddar

I. Automates à pile déterministes

Exercice 1

1.

L_{pal} ≝ \lbrace w\$w^R \mid w ∈ \lbrace a, b \rbrace^\ast \rbrace

Pour abréger les notations, $x$ dénotera un élément quelconque de l’alphabet de pile $\lbrace A, B, \bot \rbrace$.

L’automate à pile $𝒜_{pal}$ suivant, tel que 𝛴 ≝ \lbrace a, b, \$ \rbrace, 𝛤 ≝ \lbrace A, B, \bot \rbrace

  digraph {
    rankdir=LR;
    q_f[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_f[label="𝜀, ⊥/𝜀"];
  }

reconnaît $L_{pal}$.

  • en effet :

    • on voit aisément que tout mot de $L_{pal}$ est reconnu par $𝒜_{pal}$

    • et réciproquement : si w'∈ \lbrace a, b, \$ \rbrace^\ast est reconnu par $𝒜_{pal}$, alors il existe $𝛾∈𝛤^\ast$ tel que :

      q_0, \bot \; \overset{w}{⟶}_𝒜 \; q_f, 𝛾

      Or, la seule transition allant en $q_f$ est $(q_1, \bot, 𝜀, q_f, 𝜀)$, où $\bot$ est le fond de pile. Donc $𝛾 = 𝜀$.

      On peut ensuite remarquer qu’au cours de l’exécution de $𝒜_{pal}$ sur $w’$, le nombre de transitions effectuées de $q_0$ à $q_0$ est égal au nombre de transitions de $q_1$ à $q_1$.

      • en effet : toutes les transitions de l’état $q_0$ dans lui-même ajoutent un symbole sur la pile, la transition de $q_0$ à $q_1$ laisse la pile inchangée, et toutes les transitions de $q_1$ dans lui-même suppriment un symbole la pile. Comme la pile est initialisée avec le fond de pile $\bot$, lequel est supprimé de $q_1$ à $q_2$, le résultat s’ensuit.

      Il vient donc, par définition de $𝒜_{pal}$, que

      q_0, \bot \; \overset{w}{⟶}_𝒜 \; q_f, 𝛾

      est de la forme :

      \left.\begin{align*} q_0, \bot \; &\overset{w_1}{⟶}_𝒜 \; q_0, 𝛾_1 \; \overset{w_2}{⟶}_𝒜 \; ⋯ \; \overset{w_i}{⟶}_𝒜 \; q_0, 𝛾_i \\ \; &\overset{\$}{⟶}_𝒜 \; q_1, 𝛾_i \\ \; &\overset{w_{i+1}}{⟶}_𝒜 \; q_1, 𝛾_1' \; \overset{w_{i+2}}{⟶}_𝒜 \; ⋯ \; \overset{w_{2i}}{⟶}_𝒜 \; q_1, \underbrace{𝛾_i'}_{= \bot} \\ \; &\overset{𝜀}{⟶}_𝒜 \; q_f, 𝜀 \\ \end{align*} \right) ⊛

      où $∀j, w_j∈ \lbrace a, b \rbrace$

      Montrons que $w’$ est de la forme :

      w\$w^R

      où $w ∈ \lbrace a, b \rbrace^\ast$, par induction sur la taille (impaire) de $w’$.

      • si $\vert w’ \vert = 1$ : alors $w’ = $$ nécessairement, et le résultat est acquis.

      • si $w' ≝ w_1 ⋯ w_i \$ w_{i+1} ⋯ w_{2i}$ (où $i≥1 ∧ ∀j, w_j∈ \lbrace a, b\rbrace$, par $⊛$) et $\vert w \vert > 1$ :

        Par $⊛$, et comme les transitions de $q_0$ dans lui-même ne font qu’ajouter un symbole au-dessus du sommet de la pile, et les transitions de $q_1$ dans lui-même ne font que supprimer le symbole de sommet de pile, on a :

        \left.\begin{align*} q_0, \bot \; &\overset{w_2}{⟶}_𝒜 \; q_0, 𝜁_1 \; \overset{w_3}{⟶}_𝒜 \; ⋯ \; \overset{w_i}{⟶}_𝒜 \; q_0, 𝜁_i \\ \; &\overset{\$}{⟶}_𝒜 \; q_1, 𝜁_i \\ \; &\overset{w_{i+1}}{⟶}_𝒜 \; q_1, 𝜁_1' \; \overset{w_{i+2}}{⟶}_𝒜 \; ⋯ \; \overset{w_{2i-1}}{⟶}_𝒜 \; q_1, \underbrace{𝜁_i'}_{= \bot} \\ \; &\overset{𝜀}{⟶}_𝒜 \; q_f, 𝜀 \\ \end{align*} \right) ⊛⊛

        (avec $w_2 ⋯ w_i$, $w_{i+1} ⋯ w_{2i-1}$ éventuellement vides) : le premier symbole ajouté sur la pile est le dernier enlevé.

        Donc $w_2 ⋯ w_i\$ w_{i+1} ⋯ w_{2i-1} ∈ L(𝒜_{pal})$, et par hypothèse d’induction :

        w_{i+1} ⋯ w_{2i-1} = (w_2 ⋯ w_i)^R

        Supposons maintenant que $w_1 = a$. Par définition de $𝒜_{pal}$, $A$ est le premier symbole ajouté (au-dessus du fond de pile) : par $⊛$, il apparaît donc (d’après les considérations précédentes) qu’il a été enlevé par la transition

        q_1, 𝛾_{i-1}' \overset{w_{2i}}{⟶}_𝒜 \; q_1, \underbrace{𝛾_i'}_{= \bot}

        d’où, par construction de $𝒜_{pal}$ :

        w_{2i} = a

        On montre de même que si $w_1 = b$, $w_{2i} = b$, donc dans tous les cas : $w_1 = w_{2i}$, et :

        w' ≝ w_1 w_2 ⋯ w_i \$ (w_2 ⋯ w_i)^R w_{2i} = w_1 w_2 ⋯ w_i \$ (w_2 ⋯ w_i)^R w_1 \\ = w_1 w_2 ⋯ w_i \$ (w_1 w_2 ⋯ w_i)^R

        et le résultat est acquis.

En outre, on vérifie aisément que $𝒜_{pal}$ est déterministe, donc :

L_{pal} ≝ \lbrace w\$w^R \mid w ∈ \lbrace a, b \rbrace^\ast \rbrace est déterministe.

2.

L_h ≝ \lbrace w\$(h(w))^R \mid w ∈ 𝛴^+ \rbrace

Pour abréger les notations, $x$ dénotera un élément quelconque de l’alphabet de pile $𝛴∪\lbrace \bot \rbrace$.

On pose

𝒜_{pal} ≝ ⟨\lbrace q_0, q_1, q_f \rbrace, \underbrace{𝛴∪ 𝛥 ∪ \lbrace \$ \rbrace}_{\text{alphabet d'entrée}} , \underbrace{𝛴 ∪ \lbrace \bot \rbrace}_{\text{alphabet de pile}}, 𝛿, q_0, \bot, \lbrace q_f \rbrace⟩

où :

𝛿 ≝ \lbrace (q_0, x, a, q_0, xa) \mid a ∈ 𝛴 \rbrace \\ ∪ \lbrace (q_0, x, \$, q_1, x) \rbrace \\ ∪ \lbrace (q_1, a, h(a), q_1, 𝜀) \mid a ∈ 𝛴 \rbrace \\ ∪ \lbrace (q_1, \bot, 𝜀, q_f, 𝜀) \rbrace
  digraph {
    rankdir=LR;
    q_f[shape="doublecircle"];
    ⊥ -> q_0;
    q_0 -> q_0[label="∀a∈𝛴 : a, x/xa"];
    q_0 -> q_1[label="$, x/x"];
    q_1 -> q_1[label="∀a∈𝛴 : h(a), a/𝜀"];
    q_1 -> q_f[label="𝜀, ⊥/𝜀"];
  }

reconnaît $L_{pal}$.

  • en effet :

    • on voit aisément que tout mot de $L_{pal}$ est reconnu par $𝒜_{pal}$

    • et réciproquement : si $w'∈ 𝛴 ∪ 𝛥 ∪ \lbrace \$ \rbrace$ est reconnu par $𝒜_{pal}$, on montre de la même manière que dans la question précédente qu’on a :

      q_0, \bot \; \overset{w}{⟶}_𝒜 \; q_f, 𝜀

      Et que $q_0, \bot \; \overset{w}{⟶}_𝒜 \; q_f, 𝜀$ est de la forme :

      \left.\begin{align*} q_0, \bot \; &\overset{w_1}{⟶}_𝒜 \; q_0, 𝛾_1 \; \overset{w_2}{⟶}_𝒜 \; ⋯ \; \overset{w_i}{⟶}_𝒜 \; q_0, 𝛾_i \\ \; &\overset{\$}{⟶}_𝒜 \; q_1, 𝛾_i \\ \; &\overset{w_{i+1}}{⟶}_𝒜 \; q_1, 𝛾_1' \; \overset{w_{i+2}}{⟶}_𝒜 \; ⋯ \; \overset{w_{2i}}{⟶}_𝒜 \; q_1, \underbrace{𝛾_i'}_{= \bot} \\ \; &\overset{𝜀}{⟶}_𝒜 \; q_f, 𝜀 \\ \end{align*} \right) ⊛

      où $∀j, w_j∈ 𝛴 ∪ 𝛥$

      Montrons que $w’$ est de la forme :

      w\$(h(w))^R

      où $w ∈ 𝛴^+$, par induction sur la taille (impaire) de $w’$.

      • si $\vert w’ \vert = 1$ : alors $w’ = $$ nécessairement, et le résultat est acquis.

      • si $w' ≝ w_1 ⋯ w_i \$ w_{i+1} ⋯ w_{2i}$ (où $i≥1 ∧ ∀j, w_j∈ 𝛴 ∪ 𝛥$, par $⊛$) et $\vert w \vert > 1$ :

        Par $⊛$, et comme les transitions de $q_0$ dans lui-même ne font qu’ajouter un symbole au-dessus du sommet de la pile, et les transitions de $q_1$ dans lui-même ne font que supprimer le symbole de sommet de pile, on montre exactement de la même manière que dans la question précédente (avec l’hypothèse d’induction) que :

        w_{i+1} ⋯ w_{2i-1} = (h(w_2 ⋯ w_i))^R
        • Si $w_1 ≝ a∈𝛴$ :

          Par définition de $𝒜_{pal}$, $a∈𝛴$ est le premier symbole ajouté (au-dessus du fond de pile) : par $⊛$, il apparaît donc qu’il a été enlevé par la transition

          q_1, 𝛾_{i-1}' \overset{w_{2i}}{⟶}_𝒜 \; q_1, \underbrace{𝛾_i'}_{= \bot}

          Dans $𝛿$, la seule transition allant de $q_1$ dans $q_1$ et qui remplace $a∈𝛴$ par $𝜀$ est $(q_1, a, h(a), q_1, 𝜀)$. Donc :

          w_{2i} = h(a) = h(w_1)

          Par suite :

          \begin{align*} w' &= w_1 w_2 ⋯ w_i \$ (h(w_2 ⋯ w_i))^R w_{2i}\\ &= a w_2 ⋯ w_i \$ (h(w_2 ⋯ w_i))^R h(w_1) \\ &= w_1 w_2 ⋯ w_i \$ (h(w_1)h(w_2 ⋯ w_i))^R \\ &= w_1 w_2 ⋯ w_i \$ (h(w_1 w_2 ⋯ w_i))^R &&\text{(car } h \text{ est un morphisme)} \end{align*}
        • Si $w_1 ≝ d∈𝛥$ :

          Dans $𝛿$, les seules transitions qui étiquetées par des lettres (de l’alphabet d’entrée) appartenant à $𝛥$ vont de $q_1$ à $q_1$.

          Donc la transition

          q_0, \bot \; \overset{w_1}{⟶}_𝒜 \; q_0, 𝛾_1 \;

          ne peut pas avoir lieu, ce qui contredit $⊛$. Ce cas est donc exclus.

        Dans tous les cas, le résultat est acquis.

En outre, $𝒜_{pal}$ est déterministe, puisque :

  1. La seule $𝜀$-transition est $(q_1, \bot, 𝜀, q_f, 𝜀)$, et il n’existe aucune autre transition depuis $q_1, \bot$

  2. Pour tous $q∈ \lbrace q_0, q_1, q_f \rbrace, z∈\underbrace{𝛴 ∪ \lbrace \bot \rbrace}_{\text{alphabet de pile}}, b∈\underbrace{𝛴∪ 𝛥 ∪ \lbrace \$ \rbrace}_{\text{alphabet d'entrée}}$, il existe au plus une transition depuis $q, z$ en lisant $b$ :

    • Si $q=q_0$ :

      • si $b∈𝛴$ : La seule transition applicable est $(q_0, z, b, q_0, zb)$.

      • si $b∈𝛥$ ou $b = $$ : aucune transition n’est applicable.

    • Si $q=q_1$ :

      • si $b∈𝛴$ : aucune transition n’est applicable.

      • si $b∈𝛥$ : si $z∈𝛴$ et $b=h(z)$, la seule transition applicable est $(q_1, z, h(z), q_1, 𝜀)$.

        Sinon : aucune transition n’est applicable.

      • si $b = \$$ : la seule transition applicable est l’$𝜀$-transition précédemment citée

    • Si $q=q_f$ : aucune transition n’est applicable.

On a donc montré que

L_h ≝ \lbrace w\$(h(w))^R \mid w ∈ 𝛴^+ \rbrace est déterministe.

3.

Soit $L$ un langage régulier. Montrons qu’il est déterministe hors-contexte.

$L$ est reconnu par un automate

𝒜 ≝ ⟨Q, 𝛴, 𝛿, q_0, F⟩

qu’on peut supposer déterministe et sans $𝜀$-transition, quitte à le déterminiser (avec l’automate des parties par exemple).

L’idée est cet automate peut être vu comme un automate à pile qui n’utilise pas sa pile : si on pose

𝒜_{PDA} ≝ ⟨Q, 𝛴, \lbrace \bot \rbrace, 𝛿', q_0, \bot, F⟩

avec

𝛿' ≝ \lbrace (q, \bot, a, q', \bot) \mid (q, a, q')∈𝛿 \rbrace

On vérifie aisément que :

  • L’automate $𝒜$ et l’automate à pile $𝒜_{PDA}$ reconnaissent le même langage (i.e $L$) :

    en effet : tout mot reconnu par $𝒜$ est clairement reconnu par $𝒜_{PDA}$, et réciproquement, puisque la pile de $𝒜_{PDA}$ reste inchangée.

  • L’automate $𝒜_{PDA}$ hérite du déterminisme de $𝒜$ :

    en effet : Pour tous $(q, z=\bot, b) ∈ Q × \lbrace \bot \rbrace × 𝛴$, le déterminisme de $𝒜$ implique qu’il existe au plus une transition de la forme $(q, b, q’)$ (où $q’∈Q$) dans $𝛿$; donc, par construction de $𝛿’$, il existe au plus une transition de la forme $(q, z, b, q’)$ (où $q’∈Q$) dans $𝛿’$.

    Par ailleurs, il n’existe pas d’$𝜀$-transition.

On a donc montré que

Tout langage régulier est déterministe hors-contexte.

Exercice 2

Soit $L$ un langage hors-contexte.

Montrons que

il existe un DPDA ${\cal A} ≝ ⟨Q, 𝛴, 𝛤, 𝛿, q_0, z_0⟩$ tel que $L = N({\cal A})$ si, et seulement si $L$ est déterministe et préfixe.

$⟹$ :

Supposons qu’il existe un DPDA ${\cal A} ≝ ⟨Q, 𝛴, 𝛤, 𝛿, q_0, z_0⟩$ tel que $L = N({\cal A})$.

Montrons que $L$ est déterministe et préfixe.

$L$ est déterministe

On construit, de la même manière que dans le cours, l’automate à pile suivant :

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

𝛿' ≝ 𝛿 ∪ \lbrace (q, \bot, 𝜀, q_f, 𝜀) \mid q∈F \rbrace
  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="𝜀, ⊥/𝜀"];
  }

NB : on rajoute un nouveau fond de pile $\bot$, et pour chaque $q∈Q$ tel que la pile est “vide” (avec notre nouveau fond), on ajoute l’$𝜀$-transition $q, \bot \overset{𝜀}{⟶} q_f, 𝜀$

On a démontré en cours que

L({\cal A}') = N({\cal A})

De plus, ${\cal A}’$ est clairement déterministe, puisque pour tous $(q, z)) ∈ Q \sqcup \lbrace q_f \rbrace × 𝛤 \sqcup \lbrace \bot \rbrace$ :

  • si $q = q_f$ : aucune transition ne part de $q$

  • sinon, si $q∈Q$ :

    • si $z∈𝛤$ : les transitions partant de $(q, z)$ sont celles de ${\cal A}$, qui est déterministe.

    • si $z = \bot$ : la seule transition qui part de $(q, \bot)$ est l’$𝜀$-transition $(q, \bot, 𝜀, q_f, 𝜀)∈𝛿’$

Donc $L$ est déterministe.

$L$ est préfixe

Si n’était pas le cas, il existerait un mot $w ≝ w_1 \underbrace{w_2}_{\text{de longueur }≥1} ∈ L$ avec $w_1∈L$.

Par conséquent, comme $L = N({\cal A})$, il existerait $q_1, q_1’, q_2∈ Q$ tels que :

\begin{cases} q_0, z_0 \overset{w_1}{⟶}_{\cal A} q_1, 𝜀 \quad \text{(car } w_1∈L \text{)}\\ q_0, z_0 \overset{w_1}{⟶}_{\cal A} q_1', 𝛾 \overset{w_2}{⟶^+}_{\cal A} q_2, 𝜀 \quad \text{(car } w_2∈L \text{ et } \vert w_2 \vert > 0 \text{)}\\ \end{cases}

Mais alors le déterminisme de ${\cal A}$ impliquerait :

\begin{cases} q_1' = q_1 \\ 𝛾 = 𝜀 \end{cases}

Et

q_1, 𝜀 \overset{w_2}{⟶^+}_{\cal A} q_2, 𝜀

devient alors absurde puisque qu’aucune transition ne peut partir de $(q_1, 𝜀)$, car la pile est vide.

Le résultat est donc acquis.

$⟸$ :

Supposons qu’il existe un DPDA ${\cal A}’ ≝ ⟨Q’, 𝛴’, 𝛤’, 𝛿’, q_0’, z_0’, F’⟩$ reconnaissant $L$ et que $L$ est préfixe.

Montrons qu’il existe un DPDA ${\cal A} ≝ ⟨Q, 𝛴, 𝛤, 𝛿, q_0, z_0⟩$ tel que $L = N({\cal A})$.


Notons déjà qu’on peut supprimer toutes les transitions sortant d’un état final de ${\cal A}’$ sans changer le langage reconnu par ${\cal A}’$ (qui reste $L$) puisque $L$ est préfixe :

En effet : montrons que pour toute exécution de la forme

q_0', z_0' \overset{w_1}{⟶}_{\cal A'} \underbrace{q_F'}_{∈F'}, 𝛾_F' \overset{w_2}{⟶^+}_{\cal A'} q_2', 𝛾_2' \quad \text{(avec } \vert w_2 \vert > 0 \text{)}

nécessairement : $w_1 w_2∉ L({\cal A’})=L$.

Par l’absurde : si $w_1 w_2∈ L({\cal A’})=L$, alors comme $w_1∈L$ (puisque $q_0', z_0' \overset{w_1}{⟶}_{\cal A'} \underbrace{q_F'}_{∈F'}, 𝛾_F'$) et $\vert w_2 \vert>0$, $L$ ne serait pas préfixe.


Pour ne pas alourdir les notations, on note encore ${\cal A}’ ≝ ⟨Q’, 𝛴’, 𝛤’, 𝛿’, q_0’, z_0’, F’⟩$ l’automate obtenu en supprimant toutes les transitions sortant d’un état final.

On construit alors, de la même manière que dans le cours, l’automate à pile (qui accepte par pile vide) suivant :

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

𝛿 ≝ 𝛿' ∪ \lbrace (q,z, 𝜀, q_f, 𝜀) \mid q∈F'\sqcup \lbrace q_f \rbrace, z∈𝛤' \sqcup \lbrace \bot \rbrace \rbrace
  digraph {
    rankdir=LR;
    subgraph cluster_0 {
      label="𝒜"
    subgraph cluster_1 {
      label="𝒜'"
        q_1[label="q_1'", shape=doublecircle, style=dashed]; q_2[label="q_2'", shape="doublecircle", style=dashed]; q_3[label="q_3'", shape="doublecircle", style=dashed]; ⋯;
    }
    ⊥z_0[label="⊥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/𝜀"]
  }

NB : on rajoute un nouveau symbole de fond de pile $\bot$, et on ajoute des $𝜀$-transitions partant des anciens états finals vers un nouvel état $q_f$ qui vide la pile.

On a démontré en cours que

N({\cal A}) = L({\cal A}') = L

De plus, ${\cal A}$ est déterministe, puisque pour tous $(q, z, b) ∈ Q’ \sqcup \lbrace q_f \rbrace × 𝛤’ \sqcup \lbrace \bot \rbrace × 𝛴$ :

  • si $q = q_f$ : la seule transition partant de $(q, z)$ est l’$𝜀$-transition $(q_f, z, 𝜀, q_f, 𝜀)$.

  • sinon, si $q∈Q’\backslash F’$ :

    • si $z∈𝛤’$ : les transitions partant de $(q, z)$ sont celles de ${\cal A}’$, qui est déterministe.

    • si $z = \bot$ : aucune transition ne part de $(q, \bot)$.

  • sinon, si $q∈ F’$ :

    comme on a supprimé toutes les transitions sortant d’un état final dans ${\cal A}’$, la seule transition qui part de $(q, z)$ est l’$𝜀$-transition $(q, z, 𝜀, q_f, 𝜀)∈𝛿’$

Donc le résultat est acquis.


On a donc montré que

Pour tout langage hors-contexte $L$, il existe un DPDA ${\cal A} ≝ ⟨Q, 𝛴, 𝛤, 𝛿, q_0, z_0⟩$ tel que $L = N({\cal A})$ si, et seulement si $L$ est déterministe et préfixe.

Exercice 3

1.

Comme on l’a vu en TD, l’automate $𝒜$ suivant (avec $𝛴 ≝ \lbrace a, b \rbrace, 𝛤 ≝ \lbrace A, B, \bot \rbrace$) reconnaît $L≝ \lbrace a^n b^n \mid n>0 \rbrace ∪ \lbrace a^n b^{2n}\mid n>0 \rbrace$ :

  digraph {
    rankdir=LR;
    q_3[shape="doublecircle"];
    ⊥ -> q_0;
    q_0 -> q_0[label="a, z/zA"];
    q_0 -> q_1[label="𝜀, */*"];
    q_1 -> q_1[label="b, A/𝜀"];
    q_0 -> q_2[label="𝜀, */*"];
    q_2 -> q_2[label="b, A/B | b, B/𝜀"];
    q_1 -> q_3[label="𝜀, ⊥/⊥"];
    q_2 -> q_3[label="𝜀, ⊥/⊥"];
  }

En effet :

Tout mot de $L$ est clairement reconnu, et réciproquement, si $w ≝ w_1 ⋯ w_{m+n} ∈ L(𝒜)$ (où les $w_i ∈ \lbrace a, b \rbrace$):

  • soit l’exécution de $𝒜$ sur $w$ passe par $q_1$ :

    Alors elle est de la forme :

    q_0, \underbrace{𝛾_0}_{= \bot} \overset{w_1}{⟶} ⋯ \overset{w_m}{⟶} q_0, 𝛾_m \overset{𝜀}{⟶} q_1, 𝛾_m \overset{w_{m+1}}{⟶} ⋯ \overset{w_{m+n}}{⟶} q_1, 𝛾_{m+n} \overset{𝜀}{⟶} q_3, \bot

    Comme l’exécution est acceptante, elle se termine nécessairement par l’unique transition $q_1, \bot \overset{𝜀}{⟶} \underbrace{q_3}_{\text{unique état final}}, \bot$, et la pile est dans le même état qu’au départ (il n’y a que le fond de pile) :

    𝛾_{m+n}= \bot \quad ⊛

    Or :

    • toutes les transitions de $q_0$ dans $q_0$ empilent un $A$, et seulement à la lecture de la lettre $a$. Donc :

      \begin{cases} w_1 = ⋯ = w_m = a \\ ∀i∈⟦1, m⟧,\; 𝛾_i = \bot \overbrace{A ⋯ A }^{i \text{ fois}} &&\text{ (par une récurrence immédiate sur } m \text{)} \end{cases}
    • l’unique transition de $q_0$ vers $q_1$ est une $𝜀$-transition qui laisse la pile inchangée
    • toutes les transitions de $q_1$ dans $q_1$ dépilent un $A$, et seulement à la lecture de la lettre $b$. Donc, de même (par une récurrence immédiate sur $n$) :

      \begin{cases} w_{m+1} = ⋯ = w_{m+n} = b \\ ∀i∈⟦m+1, m+n⟧,\; 𝛾_i = \bot \overbrace{A ⋯ A }^{m - (i-m) = 2m-i \text{ fois}} \quad ⊛⊛ \end{cases}
    • l’unique transition de $q_2$ vers $q_3$ est une $𝜀$-transition qui la pile inchangée

    Comme

    𝛾_{m+n} = \begin{cases} \bot &&\text{par } ⊛ \\ \bot \underbrace{A ⋯ A }_{2m-(m+n) = m-n \text{ fois}} &&\text{par } ⊛⊛ \end{cases}

    Il vient que $m-n=0$, et

    w = \underbrace{w_1 ⋯ w_n }_{=\; a^n}\, \underbrace{ w_{n+1} ⋯ w_{2n}}_{=\; b^n} ∈L
    • soit l’exécution de $𝒜$ sur $w$ passe par $q_2$ :

      Alors elle est de la forme :

      q_0, \underbrace{𝛾_0}_{= \bot} \overset{w_1}{⟶} ⋯ \overset{w_m}{⟶} q_0, 𝛾_m \overset{𝜀}{⟶} q_2, 𝛾_m \overset{w_{m+1}}{⟶} ⋯ \overset{w_{m+n}}{⟶} q_2, 𝛾_{m+n} \overset{𝜀}{⟶} q_3, \bot

      Comme l’exécution est acceptante, elle se termine nécessairement par l’unique transition $q_2, \bot \overset{𝜀}{⟶} \underbrace{q_3}_{\text{unique état final}}, \bot$, et encore une fois :

      𝛾_{m+n}= \bot \quad ⊛

      Or :

      • On montre de même que précédemment que :

        \begin{cases} w_1 = ⋯ = w_m = a \\ ∀i∈⟦1, m⟧,\; 𝛾_i = \bot \overbrace{A ⋯ A }^{i \text{ fois}} \end{cases}
      • l’unique transition de $q_0$ vers $q_2$ est une $𝜀$-transition qui laisse la pile inchangée
      • toutes les transitions de $q_2$ dans $q_2$

        • remplacent le haut de la pile par un $B$ si c’est un $A$

        ou

        • dépilent le haut de la pile si c’est un $B$

        et seulement à la lecture de la lettre $b$. Donc :

        w_{m+1} = ⋯ = w_{m+n} = b

        Et

        \begin{align*} &𝛾_{m+1} = \bot A^{m-1}B &𝛾_{m+2}=\bot A^{m-1} \\ &𝛾_{m+3} = \bot A^{m-2}B &𝛾_{m+4} = \bot A^{m-2} \\ &𝛾_{m+5} = \bot A^{m-3} B &𝛾_{m+6} = \bot A^{m-3} \\ \vdots \\ \end{align*}

        On montre ainsi par une récurrence immédiate sur $n$ que :

        ∀i∈⟦1, n⟧,\; 𝛾_{m+i} = \begin{cases} \bot A^{m-i/2} &&\text{ si } i \text{ est pair} \\ \bot A^{m-(i+1)/2} B &&\text{ sinon } \end{cases} \quad ⊛⊛
      • l’unique transition de $q_2$ vers $q_3$ est une $𝜀$-transition qui la pile inchangée

      Comme

      𝛾_{m+n} = \bot \quad\text{par } ⊛

      et

      𝛾_{m+n} = \begin{cases} \bot A^{m-n/2} &&\text{ si } n \text{ est pair} \\ \bot A^{m-(n+1)/2} B &&\text{ sinon } \end{cases} \quad \text{par } ⊛⊛

      Il vient que $n$ est pair et $m - n/2 =0$, d’où :

      w = \underbrace{w_1 ⋯ w_m }_{=\; a^m}\, \underbrace{ w_{m+1} ⋯ w_{m + 2m}}_{=\; b^{2m}} ∈L

On a donc montré que

$L≝ \lbrace a^n b^n \mid n>0 \rbrace ∪ \lbrace a^n b^{2n}\mid n>0 \rbrace$ est algébrique.

2.

a).

Soit $w ∈ L({\cal A}’)$.

Montrons que $h(w) ∈ L({\cal A})$.

L’exécution de ${\cal A}’$ sur $w$ est de la forme :

(q_0, 0), z_0 \overset{w_1}{⟶}_{\cal A'} (q_1, 0), 𝛾_1 \overset{w_2}{⟶}_{\cal A'} ⋯ \overset{w_m}{⟶}_{\cal A'} (\underbrace{q_{m}}_{∈F}, 0), 𝛾_m \\ \overset{g(w_{m+1})}{⟶}_{\cal A'} (q_{m+1}, 1), 𝛾_{m+1}\overset{g(w_{m+2})}{⟶}_{\cal A'} ⋯ \overset{g(w_{m+n})}{⟶}_{\cal A'} (\underbrace{q_{m+n}}_{∈F}, 1), 𝛾_{m+n}

(puisque qu’il n’existe aucune transition allant d’un état de $Q× \lbrace 1 \rbrace$ vers un état de $Q× \lbrace 0 \rbrace$)

  • $w = w_1 ⋯ w_m g(w_{m+1}) ⋯ g(w_{m+n})$
  • $q_0, q_1, ⋯, q_{m-1} ∉ F$
  • $q_m ∈ F$
  • $q_{m+n}∈F$ puisque $w ∈ L({\cal A}’)$ et l’ensemble des états finals de ${\cal A}’$ est $F × \lbrace 1 \rbrace$
  • $w_1, ⋯, w_m ∈ \lbrace a, b, 𝜀 \rbrace$
  • $w_{m+1}, ⋯, w_{m+n}∈ \lbrace b, 𝜀 \rbrace$

Par définition de $𝛿’$, l’exécution

q_0, z_0 \overset{w_1}{⟶}_{\cal A} q_1, 𝛾_1 \overset{w_2}{⟶}_{\cal A} ⋯ \overset{w_m}{⟶}_{\cal A} \underbrace{q_{m}}_{∈F}, 𝛾_m \\ \overset{w_{m+1}}{⟶}_{\cal A} q_{m+1}, 𝛾_{m+1} \overset{w_{m+2}}{⟶}_{\cal A} ⋯ \overset{w_{m+n}}{⟶}_{\cal A} \underbrace{q_{m+n}}_{∈ F}, 𝛾_{m+n}

est acceptante dans ${\cal A}$, et

\begin{cases} w_1 ⋯ w_m ∈ L \quad\text{ donc en particulier } w_1, ⋯, w_m ∈ \lbrace a,b,𝜀 \rbrace \\ w_1 ⋯ w_{m+n} ∈ L \end{cases}

Ainsi :

\begin{align*} h(w) & = h(w_1) ⋯ h(w_m) h(g(w_{m+1})) ⋯ h(g(w_{m+n})) &&\text{ (car } h \text{ est un morphisme)}\\ & = h(w_1) ⋯ h(w_m) w_{m+1} ⋯ w_{m+n} &&\text{ (car } h \circ g = id \text{)} \\ & = w_1 ⋯ w_m w_{m+1} ⋯ w_{m+n} &&\text{ (car } h_{\mid \lbrace a, b, 𝜀 \rbrace} = id \text{ et } w_1, ⋯, w_m ∈ \lbrace a, b, 𝜀 \rbrace \text{ )} ∈ L\\ \end{align*}

Et le résultat est acquis.

b).

Soit $w ∈ L({\cal A}’)$.

On reprend les résultats et notations de la question précédente :

  • $w = w_1 ⋯ w_m \; g(w_{m+1}) ⋯ g(w_{m+n})$
  • $w_{m+1}, ⋯, w_{m+n}∈ \lbrace b, 𝜀 \rbrace$

    • donc $g(w_{m+1}), ⋯, g(w_{m+n}) ∈ \lbrace c, 𝜀 \rbrace$
  • $w_1 ⋯ w_m ∈ L = L({\cal A})$

Il vient donc que

w ≝ w_1' w_2'

où $w_1’ ∈ L({\cal A}), w_2’ ∈ \lbrace c \rbrace^\ast$

et le résultat est acquis.

d).

Soit $w ∈ L({\cal A}’)$.

D’après b) :

w ≝ w_1' w_2'
  • $w_1’ ∈ L({\cal A}) = L$

    • donc en particulier : les lettres de $w_1’$ appartiennent à $\lbrace a, b \rbrace$, et $h(w_1’) = w_1’$ puisque $h_{\mid \lbrace a, b \rbrace} = id$
  • $w_2’ ∈ \lbrace c \rbrace^\ast$

    • donc en particulier : $h(w_2’) ∈ \lbrace b \rbrace^\ast$ puisque $h(c)=b$

Et d’après a) :

L \ni h(w) = h(w_1')h(w_2') = \underbrace{w_1'}_{∈L} \; \underbrace{h(w_2')}_{∈ \lbrace b \rbrace^\ast}

Donc deux choses l’une :

  • Soit $w_2’ = 𝜀$ :

    et

    w = w_1' ∈ L
  • Soit $\vert w_2’ \vert > 0$ :

    et comme

    \underbrace{w_1'}_{∈L} \; \underbrace{h(w_2')}_{∈ \lbrace b \rbrace^+} ∈ L

    il vient que il existe $n>0$ tel que :

    \begin{cases} w_1' h(w_2') = a^n b^{2n} ∈L \\ w_1' = a^n b^n ∈ L \\ h(w_2') = b^n \end{cases}

    Donc

    w = w_1' w_2' = a^n b^n c^n

Dans tous les cas :

w ∈ \lbrace a^n b^n c^n \mid n>0 \rbrace ∪ L

et on a montré que :

L({\cal A}') ∈ \lbrace a^n b^n c^n \mid n>0 \rbrace ∪ L

3.

Soit $n>0$.

Montrons que $a^n b^n c^n ∈ L({\cal A}’)$.

Remarquons que

a^n b^n c^n = a^n b^n g(b^n)

Or, comme

  • $a^n b^{2n} ∈L$
  • $a^n b^n ∈L$
  • ${\cal A}$ est déterministe

il existe une unique exécution de ${\cal A}$ sur $a^n b^{2n}$ :

q_0, z_0 \overset{a^nb^n}{⟶^\ast}_{\cal A} \underbrace{q_1}_{∈F}, 𝛾_1 \overset{b^n}{⟶^\ast}_{\cal A} \underbrace{q_2}_{∈F}, 𝛾_2 \quad ⊛

telle que

  • $q_1$ (resp. $q_2$) est le premier état final par lequel passe toute exécution acceptante de ${\cal A}$ sur $a^n b^n$ (resp. $a^n b^{2n}$) (${\cal A}$ est déterministe)

    • on prend cette précaution à cause de l’existence éventuelle d’$𝜀$-transitions dans ${\cal A}$ partant de $q_1$ (resp. $q_2$) dans autre état final
    • il vient donc que, hormis $q_1$, aucun état par lequel passe l’exécution $q_0, z_0 \overset{a^nb^n}{⟶^\ast}_{\cal A} q_1, 𝛾_1$ n’est final

De fait :

  • toute transition de $q_0, z_0 \overset{a^nb^n}{⟶^\ast}_{\cal A} q_1, 𝛾_1$ est de la forme :

    (q, z, d, q', 𝛾) ∈ 𝛿

    • $d ∈ \lbrace a, b, 𝜀 \rbrace$
    • $q ∉ F$
  • la première transition de $q_1, 𝛾_1 \overset{b^n}{⟶^\ast}_{\cal A} q_2, 𝛾_2$ est de la forme :

    (q, z, d, q', 𝛾) ∈ 𝛿

    • $d ∈ \lbrace b, 𝜀 \rbrace$
    • $q=q_1 ∈ F$
  • les autres transition de $q_1, 𝛾_1 \overset{b^n}{⟶^\ast}_{\cal A} q_2, 𝛾_2$ sont de la forme :

    (q, z, d, q', 𝛾) ∈ 𝛿

    • $d ∈ \lbrace b, 𝜀 \rbrace$

Donc l’exécution

\overbrace{(q_0, 0), z_0 \overset{a^n b^n}{⟶^\ast}_{\cal A'} (\underbrace{q_1}_{∈F}, 0), 𝛾_1}^{\text{les états appartiennent à } Q× \lbrace 0 \rbrace } \overbrace{\overset{ g(b)^n = c^n}{⟶^\ast}_{\cal A'} (\underbrace{q_{2}}_{∈F}, 1)}^{\text{les états appartiennent à } Q× \lbrace 1 \rbrace}

obtenue à partir de $⊛$ est bien définie et existe dans ${\cal A’}$

Comme $(q_1, 1)$ est final dans ${\cal A’}$, il en résulte donc que :

a^n b^n c^n ∈ L({\cal A'})

et le résultat est acquis.

\lbrace a^n b^n c^n \mid n>0 \rbrace ⊆ L({\cal A'})

4.

D’après 2. c) et 3. :

\lbrace a^n b^n c^n \mid n>0 \rbrace ⊆ L({\cal A'}) ⊆ \lbrace a^n b^n c^n \mid n>0 \rbrace ∪ L

Donc en intersectant avec le langage régulier $\lbrace a, b, c \rbrace^\ast c$ :

\underbrace{\lbrace a^n b^n c^n \mid n>0 \rbrace ∩ \lbrace a, b, c \rbrace^\ast c}_{ = \; \lbrace a^n b^n c^n \mid n>0 \rbrace} ⊆ L({\cal A'}) ∩ \lbrace a, b, c \rbrace^\ast c ⊆ \underbrace{\Big(\lbrace a^n b^n c^n \mid n>0 \rbrace ∩ \lbrace a, b, c \rbrace^\ast c\Big)}_{ = \; \lbrace a^n b^n c^n \mid n>0 \rbrace} ∪ \underbrace{\Big( L ∩ \lbrace a, b, c \rbrace^\ast c \Big)}_{ = \; ∅}

Donc

L({\cal A'}) ∩ \lbrace a, b, c \rbrace^\ast c = \lbrace a^n b^n c^n \mid n>0 \rbrace

Or

  • $L({\cal A’}) ∩ \lbrace a, b, c \rbrace^\ast c$ est algébrique, en tant qu’intersection d’un langage algébrique et d’un langage régulier (d’après le corollaire 1 de la section “Théorème de Bar-Hillel” du cours)

  • $\lbrace a^n b^n c^n \mid n>0 \rbrace$ n’est pas algébrique (d’après l’EX 2. 1) du TD5) :

    • Supposons que $L ≝ \lbrace a^n b^n c^n \mid n≥0\rbrace$ est algébrique.

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

      • $L(G)=L$
      • $K$ est l’entier donné par le lemme d’Ogden, dont l’énoncé est rappelé ici.

      Soit $w = a^K b^K c^K$ (où les $a$ sont distingués, par exemple).

      Il existe $w = 𝛼 u 𝛽 v 𝛾$ tq $𝛼 u^n 𝛽 v^n 𝛾 ∈ L$ pour tout $n$, et $u≠𝜀$ ou $v≠𝜀$ (par le point c) du lemme d’Ogden).

      Comme $𝛼 u^2 𝛽 v^2 𝛾 ∈ L ⊆ a^\ast b^\ast c^\ast$, $u$ ne contient que des $a$ ou que des $b$ ou que des $c$, et de même pour $v$.

      Or un des deux mots parmi $u$ et $v$ est non vide, et on n’a pas les trois lettres dans ces deux mots, donc $𝛼 u^n 𝛽 v^n 𝛾 ∈ L$ pour tout $n$, c’est absurde.

On obtient donc une contradiction, et :

$L≝ \lbrace a^n b^n \mid n>0 \rbrace ∪ \lbrace a^n b^{2n}\mid n>0 \rbrace$ n’est pas déterministe.

Exercice 4

1.

Réduisons le complémentaire du problème de correspondance de Post au problème de l’intersection vide $𝒫_{int_vide}$

On se donne une instance du problème de correspondance de Post :

  • $𝛴_{Post}$ un alphabet tel que $𝛴_{Post} \not\ni $$
  • $n∈ ℕ$
  • $u_1, ⋯, u_n ∈ 𝛴_{Post}^+$
  • $v_1, ⋯, v_n ∈ 𝛴_{Post}^+$

Soit $𝛴$ un alphabet à $n$ lettres $a_1, ⋯, a_n$ tel que

𝛴∩(𝛴_{Post}∪ \lbrace \$ \rbrace) = ∅

On note $h_u$ (resp. $h_v$) le morphisme qui, à chaque $a_i$, associe $u_i$ (resp. $v_i$).

On construit, de la même manière que dans l’exercice 1, deux automates à pile déterministes $𝒜_u$ et $𝒜_v$ reconnaissant respectivement :

L_u ≝ \lbrace w \$ (h_u(w))^R \mid w∈𝛴^+ \rbrace

et

L_v ≝ \lbrace w \$ (h_v(w))^R \mid w∈𝛴^+ \rbrace

La fonction qui calcule ces deux automates est bien calculable.

De plus :

  • si l’instance du problème de correspondance de Post est positive :

    il existe $k ∈ ⟦1, n⟧$ et des indices $i_1, ⋯, i_k ∈ ⟦1, n⟧$ tels que :

    u_{i_1} ⋯ u_{i_k} = v_{i_1} ⋯ v_{i_k}

    donc

    h_u(a_{i_1}) ⋯ h_u(a_{i_k}) = u_{i_1} ⋯ u_{i_k} = v_{i_1} ⋯ v_{i_k} = h_v(a_{i_1}) ⋯ h_v(a_{i_k})

    et

    L_u \ni a_{i_1} ⋯ a_{i_k} \$ (h_u(a_{i_1}) ⋯ h_u(a_{i_k}))^R \\ = a_{i_1} ⋯ a_{i_k} \$ (h_v(a_{i_1}) ⋯ h_v(a_{i_k}))^R ∈ L_v

    Donc $L_u ∩ L_v ≠ ∅$

  • Si $L_u ∩ L_v ≠ ∅$ :

    Alors il existe :

    L_u \ni a_{i_1} ⋯ a_{i_k} \$ (h_u(a_{i_1}) ⋯ h_u(a_{i_k}))^R \\ = a_{j_1} ⋯ a_{j_r} \$ (h_v(a_{j_1}) ⋯ h_v(a_{j_r}))^R ∈ L_v

    Comme $\$ ∉ 𝛴$ :

    \begin{cases} a_{i_1} ⋯ a_{i_k} = a_{j_1} ⋯ a_{j_r} \\ h_u(a_{i_1}) ⋯ h_u(a_{i_k}) = h_v(a_{j_1}) ⋯ h_v(a_{j_r}) \end{cases}

    Donc $k=r$, $(i_1, ⋯, i_k) = (j_1, ⋯, j_k)$, et :

    u_{i_1} ⋯ u_{i_k} = h_u(a_{i_1}) ⋯ h_u(a_{i_k}) = h_v(a_{j_1}) ⋯ h_v(a_{j_r}) = v_{i_1} ⋯ v_{i_k}

    Donc l’instance du problème de correspondance de Post est positive.

On a montré que :

l’instance de problème de correspondance de Post est positive si, et seulement si l’instance $(L_u, L_v)$ de $𝒫_{int_vide}$ est négative.

Soit :

l’instance de problème de correspondance de Post est négative si, et seulement si l’instance $(𝒜_u, 𝒜_v)$ de $𝒫_{int_vide}$ est positive, et

On a réduit $co-PCP$, qui est indécidable, à $𝒫_{int_vide}$ : $𝒫_{int_vide}$ est donc indécidable.

2.

a).

On réduit $𝒫_{int_vide}$ à ce problème $𝒫_{inclusion}$.

Soit $(𝒜_1, 𝒜_2)$ une instance de $𝒫_{int_vide}$ ($𝒜_1, 𝒜_2$ sont des DPDA).

On construit l’automate à pile déterministe $\overline{𝒜_2}$ qui reconnaît $𝛴^\ast \backslash L(𝒜_2)$ avec le théorème de clôture par complémentation.

La fonction qui calcule cet automate est bien calculable.

De plus :

L(𝒜_1) ∩ L(𝒜_2) = ∅ ⟺ L(𝒜_1) ⊆ 𝛴^\ast \backslash L(𝒜_2) = L(\overline{𝒜_2})

d’où :

$(𝒜_1, 𝒜_2)$ est une instance positive de $𝒫_{int_vide}$ si, et seulement si $(𝒜_1, \overline{𝒜_2})$ est une instance positive de $𝒫_{inclusion}$.

On a donc réduit $𝒫_{int_vide}$, qui est indécidable, à $𝒫_{inclusion}$ : $𝒫_{inclusion}$ est donc indécidable.

b).

On réduit $𝒫_{int_vide}$ à ce problème $𝒫_{univ}$.

Soit $(𝒜_1, 𝒜_2)$ une instance de $𝒫_{int_vide}$ ($𝒜_1, 𝒜_2$ sont des DPDA).

On construit les automates à pile déterministes $\overline{𝒜_1}$ et $\overline{𝒜_2}$ qui reconnaissent respectivement $𝛴^\ast \backslash L(𝒜_1)$ et $𝛴^\ast \backslash L(𝒜_2)$, avec le théorème de clôture par complémentation.

Puis, on construit l’automate à pile $𝒜_{union}$ reconnaissant $𝛴^\ast \backslash L(𝒜_1) ∪ 𝛴^\ast \backslash L(𝒜_2)$ (d’après l’EX 3. 3) du TD4), les langages algébriques sont clos par union).

La fonction qui calcule ces automates est bien calculable.

De plus :

L(𝒜_1) ∩ L(𝒜_2) = ∅ ⟺ 𝛴^\ast \backslash \big(L(𝒜_1) ∩ L(𝒜_2)\big) = 𝛴^\ast \\ ⟺ \underbrace{𝛴^\ast \backslash L(𝒜_1) ∪ 𝛴^\ast \backslash L(𝒜_2)}_{= \; L(𝒜_{union})} = 𝛴^\ast

d’où :

$(𝒜_1, 𝒜_2)$ est une instance positive de $𝒫_{int_vide}$ si, et seulement si $𝒜_{union}$ est une instance positive de $𝒫_{univ}$.

On a donc réduit $𝒫_{int_vide}$, qui est indécidable, à $𝒫_{univ}$ : $𝒫_{univ}$ est donc indécidable.

Leave a comment