DM : Automates à pile déterministes

DM de Langages Formels

Younesse Kaddar

• Énoncé

• Version PDF

• http://younesse.net/Langages-formels/DM_LangagesFormels/

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 ⟩\]

où

\[𝛿' ≝ 𝛿 ∪ \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'⟩\]

où

\[𝛿 ≝ 𝛿' ∪ \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$)

où

• $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', 𝛾) ∈ 𝛿\]

  où

  • $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', 𝛾) ∈ 𝛿\]

  où

  • $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', 𝛾) ∈ 𝛿\]

  où

  • $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.