TD 5 : Lemme d’Ogden
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$
$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\]
Leave a comment