TD 5 : Lemme d’Ogden

Énoncé

EX 1

1.

On va construire une injection de l’ensemble des feuilles distinguées dans l’ensemble des $r$-uplets à valeurs dans $⟦1,m⟧$.

À chaque feuille $f$, on associe le $r$-uplet $(m_1, ⋯, m_r)$ où, $m_i$ est le numéro du fils du $i$-ème noeud distingué de la branche reliant $f$ à la racine de $t$.


Par réc sur $r$ :

  • Pour $r=0$ : Ok

  • Pour $r>0$ :

    Soit $x$ un noeud spécial qui n’a pas d’ancêtre spécial.

    Montrons que tout noeud distingué $y$ est soit un ancêtre de $x$, soit un descendant de $x$.

    • Par l’absurde : sinon, le plus petit ancêtre commun de $x$ et $y$ serait spécial

    Toutes les feuilles distinguées de $t$ sont dans le sous-arbre $t_x$ enraciné à $x$.

    $x$ a au plus $m$ fils.

    Par HR, chacun des sous-arbres enracinés en les fils de $x$ contiennent au plus $m^{r-1}$ feuilles distinguées.

    Donc $t_x$ contient au plus $m^r$ feuilles distinguées, et il en est de même de $t$.

2.

On pose

  • $m ≝ \max \lbrace \vert 𝛼 \vert \mid ∃ (A, 𝛼)∈P \rbrace$

  • $r≝ 2 \vert N \vert + 2$

  • $K ≝ m^r+1$

Soit $w∈\widehat{L}_G(A)$ et $t$ un arbre de dérivation de $w$

$t$ est de degré au plus $m$, et a au moins $K$ feuilles distinguées, donc d’après la question 1), il existe une branche $B$ de $t$ avec $r+1 = 2 \vert N \vert+3$ noeuds spéciaux $x_0, ⋯, x_r$.

Chacun des $x_i$ a un fils distingué à gauche ou à droite de $B$.

G≝ \lbrace x_i \mid x_i \text{ a un fils distingué à gauche de } B \rbrace_{0≤i≤r}
D≝ \lbrace x_i \mid x_i \text{ a un fils distingué à droite de } B \rbrace_{0≤i≤r}

Donc

\vert D \vert + \vert G \vert > 2(\vert N \vert+1)

Donc $\vert D \vert > \vert N \vert+1$ ou $\vert G \vert > \vert N \vert+1$

Par exemple, disons que $\vert G \vert > \vert N \vert+1$.

G = \lbrace x_{i_0}, ⋯, x_{i_{\vert N \vert}}, ⋯ \rbrace

Donc il existe $i_0≤j<k≤ i_{\vert N \vert}$ tq $x_j$ et $x_k$ ont la même étiquette.

Soit $w = 𝛼u𝛽v𝛾$ la factorisation définie comme sur la figure.

$x_{i_0}$, $x_j$ et $x_k$ ont un fils distingué à gauche de $B$, donc $𝛼$, $u$, $𝛽$ contiennent une lettre distinguée.

On vérifie donc les trois premières conditions (a), (b), (c) du lemme d’Ogden.

$\vert u𝛽v \vert < \vert w \vert$, et si $u𝛽v$ contient plus de $K$ lettres distinguées, on peut le décomposer de la même manière, jusqu’à vérifier (d).

EX 2

1.

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

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

  • $L(G)=L$
  • $K$ est l’entier donné par le lemme d’Ogden

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 ( c )).

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.

2.

$L_1 ≝ \lbrace a^n b^n c^m \mid n, m ≥0 \rbrace$ est algébrique

S ⟶ Sc \mid A \mid 𝜀 \\ A ⟶ aAb \mid 𝜀

De même, $L_2 ≝ \lbrace a^n b^m c^m \mid n,m≥0 \rbrace$ est algébrique.

Et $L_1 ∩ L_2 = L$ n’est pas algébrique.

Donc les langages algébriques ne sont pas fermés par intersection.

Or les langages algébriques sont union, et $L_1 ∩ L_2 = (L_1^c ∪ L_2^c)^c$ donc les langages algébriques ne sont pas clos par complément.

EX 3.

1.

Supposons que $L_{cross} ≝ \lbrace a^n b^m c^n d^m \mid n,m≥0\rbrace$ est algébrique.

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

  • $L(G)=L_{cross}$
  • $K$ est l’entier donné par le lemme d’Ogden

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

Il existe $w = 𝛼 u 𝛽 v 𝛾$ tq $𝛼 u^N 𝛽 v^N 𝛾 ∈ L_{cross}$ pour tout $N$, et $u≠𝜀$ ou $v≠𝜀$ (par ( c )).

Donc nécessairement :

  • $u$ ne contient que des $a$, et $v$ ne contient que des $c$.

OU

  • $u$ ne contient que des $b$, et $v$ ne contient que des $d$ : impossible, car les $a$ sont marqués.

Donc

  • $𝛼 = a^i$
  • $u = a^j$
  • $𝛽 = a^k b^k c^p$
  • $v = c^j$
  • $𝛾 = c^qd^k$

On a $S ⟶^\ast 𝛼T𝛾$, i.e

S⟶^\ast \underbrace{a^i T c^q d^k}_{w'}

On applique le lemme d’Ogden à $w’$, en distinguant les $d$

$w’ = 𝛼’u’𝛽’v’𝛾’ = a^i T c^q d^k$

Par ( c ), $v’=d^{j’}$ pour un certain $j’$.

Comme $T⟶^\ast a^j a^k b^K c^p$, $j, k >0$

et que $𝛼’ u’^2 𝛽 v’^2 𝛾’ ∈ L_{cross}$, $u’$ ne contient pas $T$ (sinon on aurait $L∩a^\ast (a^\ast b^\ast c^\ast) b^\ast c^\ast ≠∅$)

$u’$ ne contient uniquement des $a$ ou des $c$ ou des $d$.

Pour tout $n$,

𝛼' u'^n 𝛽 v'^n 𝛾' = a^{k_n} T c^{j_n} d^{k_n}

avec $i_n, j_n, k_n>0$ et $(k_n)$ strictement croissante

𝛼'u'^n 𝛽' v'^n 𝛾' ⟶^\ast \underbrace{a^{i_n} a^j a^k b^K c^p c^{j_n} d^{k_n}}_{w'_n}
\vert w'_n \vert_b = K \\ \vert w'_n \vert_d > k_n

Comme $(k_n)$ strictement croissante, contredit $w’_n ∈L$ pour tout $n$.

Donc $L$ n’est pas algébrique.

2.

Supposons que $L_{copy}$ est algébrique.

Alors

L_{copy}∩a^\ast b^\ast a^\ast b^\ast = \underbrace{\lbrace a^n b^m a^n b^m \mid m,n ≥0 \rbrace}_{L_1}

est aussi algébrique.

Soit

𝜋 ≝ \begin{cases} \lbrace a, b, c, d \rbrace^\ast ⟶ \lbrace a, b \rbrace^\ast \\ a, c \mapsto a \\ b, d \mapsto b \end{cases}
𝜋^{-1}(L_1) = \lbrace (a+c)^n (b+d)^m (a+c)^n (b+d)^m \mid m,n ≥0\rbrace

est algébrique.

𝜋^{-1}(L_1)∩a^\ast b^\ast c^\ast d^\ast = L_{cross}

est algébrique : contradiction.

3.

Clôture par union.

  • $w ≝ a^{K+K!} b^K c^K$ on distingue les $b$.
  • $w = 𝛼u𝛽v𝛾$

$𝛼, u, 𝛽$ ou $𝛽, v, 𝛾$ contient des $b$.

$𝛼u^2 𝛽 v^2 𝛾 ∈ L$ donc $𝛼u^2 𝛽 v^2 𝛾 ∈ \lbrace a^n b^m c^m \mid n, m ≥0 \rbrace$ (car $K! > K$)

Comme $u$ ou $v$ contient des $b$ et $𝛼u^2 𝛽 v^2 𝛾 ∈ \lbrace a^n b^m c^m \mid n, m ≥0 \rbrace$

  • $u = b^j$
  • $v= c^j$
  • $𝛼= a^{K+K!}b^i$
  • $𝛽= b^k c^p$
  • $𝛾 = c^q$
S ⟶^\ast a^{K+K!} b^i T c^q ⟶^\ast a^{K+K!} b^i (b^j T c^j) c^q \\ ⟶^\ast ⋯ \\ ⟶^\ast a^{K+K!} b^i (b^j)^{K!/j} T (c^j)^{K!/j} c^q \\ ⟶^\ast a^{K+K!} b^i (b^j)^{K!/j} (b^kc^q) (c^j)^{K!/j} c^q

$w’ = a^K b^K c^{K+K!}$, $b$ distingués.

De même, on obtient une dérivation :

S ⟶^\ast a^{i'} T b^{q'} c^{K+K!} ⟶^\ast a^{i'} (a^{j'} T b^{j'}) b^{q'} c^{K+K!} \\ ⟶^\ast ⋯ \\ ⟶^\ast a^{i'} (a^{j'})^{K!/j'} T (b^{j'})^{K!/j'} b^{q'} c^{K+K!} \\ ⟶^\ast a^{i'} (a^{j'})^{K!/j'} (a^{k'}b^{p'}) (b^{j'})^{K!/j'} b^{q'} c^{K+K!} c^q

EX 4

Leave a comment