From dc5f7673b6a8492c153cd4119ddc94c729868f31 Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Fri, 17 Mar 2017 18:41:48 +0100
Subject: Another exercise (on various kinds of languages).

---
 controle-20170330.tex | 174 ++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 174 insertions(+)

diff --git a/controle-20170330.tex b/controle-20170330.tex
index 7532dee..1c50166 100644
--- a/controle-20170330.tex
+++ b/controle-20170330.tex
@@ -281,6 +281,180 @@ peut aussi noter $+$).
 \end{corrige}
 
 
+%
+%
+%
+
+\exercice
+
+À toutes fins utiles, on rappelle qu'un langage « algébrique » est un
+langage engendré par une grammaire hors contexte, et que
+l'intersection d'un langage algébrique et d'un langage rationnel est
+un langage algébrique.
+
+Sur l'alphabet $\Sigma = \{a,b\}$, on considère le langage $L := \{w
+a^n w^{\textsf{R}} : w\in\Sigma^*, n\in\mathbb{N}\}$, où
+$w^{\textsf{R}}$ désigne le miroir (=transposé) d'un mot $w$.
+Autrement dit, $L$ est le langage formé des mots qui peuvent s'écrire
+comme concaténation d'un mot $w$, d'un nombre quelconque
+(éventuellement nul) de $a$, puis du miroir du même mot $w$.  On
+considère aussi le langage $L' := \{w a^n w : w\in\Sigma^*,
+n\in\mathbb{N}\}$ (sans miroir sur le troisième facteur), formé des
+mots qui peuvent s'écrire comme concaténation d'un mot $w$, d'un
+nombre quelconque (éventuellement nul) de $a$, puis du même mot $w$.
+
+(1) Donner un exemple de mot appartenant à $L$ mais pas à $L'$, et un
+exemple de mot appartenant à $L'$ mais pas à $L$.
+
+(2) Proposer une grammaire hors contexte qui engendre $L$ (on pourra
+se contenter d'une justification très succincte du fait qu'elle
+engendre bien $L$).  En particulier, on retiendra que $L$ est
+algébrique (c'est tout ce qui sera nécessaire pour traiter les
+questions suivantes).
+
+(3) On \emph{admet}\footnote{Cela pourrait être démontré au moyen du
+  lemme de pompage pour les langages algébriques, mais ce n'est pas
+  demandé.} que le langage $M' := \{b^p a b^q a b^p a b^q : p,q>0\}$
+n'est pas algébrique.  (Autrement dit, $M'$ est l'ensemble des mots de
+la forme $b^p a b^q a b^p a b^q$ où $p$ et $q$ sont deux entiers
+naturels non nuls.)  En \emph{déduire} que le langage $L'$ n'est pas
+algébrique.  Justifier soigneusement.
+
+Pour cette question et les suivantes, on pourra introduire le langage
+auxiliaire $N$ dénoté par l'expression rationnelle $b^{+} a b^{+} a b^{+}
+a b^{+}$ où $b^{+}$ est une abréviation pour $bb{*}$ (dénotant au moins
+une répétition de $b$).
+
+(4a) Montrer que le langage $M := \{b^p a b^q a b^q a b^p : p,q>0\}$
+(noter la différence dans l'ordre des exposants par rapport à $M'$)
+n'est pas rationnel.\quad (4b) En \emph{déduire} que le langage $L$
+n'est pas rationnel.
+
+(5) Montrer que le langage $M$ est algébrique, sans en donner une
+grammaire.
+
+(6) Le langage $L'$ est-il décidable ?  Est-il semi-décidable ?
+
+(7) Faire un tableau indiquant, pour chacun des quatre langages
+$L,L',M,M'$ considérés dans cet exercice, et pour chacune des quatre
+propriétés « rationnel », « algébrique », « décidable »,
+« semi-décidable », si le langage en question a la propriété en
+question.
+
+\begin{corrige}
+(1) Le mot $babbabbab$ appartient à $L$ (prendre $w=babb$ et $n=1$)
+  mais pas à $L'$ ; le mot $babbababb$ appartient à $L'$ (idem) mais
+  pas à $L$.
+
+\smallbreak
+
+(2) La grammaire
+\[
+\begin{aligned}
+S &\rightarrow aSa \;|\; bSb \;|\; A\\
+A &\rightarrow \varepsilon \;|\; aA\\
+\end{aligned}
+\]
+engendre le langage $L$ : en effet, les règles $S\rightarrow aSa$ et
+$S\rightarrow bSb$ permettent de placer des $a$ et $b$ symétriquement
+autour de $S$, c'est-à-dire de produire les $wSw^{\mathsf{R}}$ et donc
+$wAw^{\mathsf{R}}$, tandis que les règles $A\rightarrow\varepsilon$ et
+$A\rightarrow aA$ reviennent à $A\rightarrow a{*}$ et permettent de
+transformer $A$ en un nombre quelconque de $a$.
+
+\smallbreak
+
+(3) Le langage $M'$ est l'intersection du langage $L'$ avec le langage
+rationnel $N$ dénoté par l'expression rationnelle $b^{+} a b^{+} a b^{+}
+a b^{+}$.  En effet, d'une part on a $M' \subseteq L' \cap N$,
+puisqu'un mot $b^p a b^q a b^p a b^q \in M'$ est évidemment dans $N$
+et par ailleurs peut s'écrire $w a w$ où $w := b^p a b^q$.  Mais
+réciproquement, on a $L'\cap N \subseteq M'$ : en effet, si pour
+certains $w \in \Sigma^*$ et $n \in \mathbb{N}$ le mot $w a^n w$ est
+dans $N$, on a forcément $n\leq 1$ car il n'y a jamais plus qu'un $a$
+consécutif dans un mot de $N$, de là on en déduit que le nombre
+$|w|_a$ de $a$ dans $w$ vaut forcément exactement $1$ et que $n=1$
+(seule possibilité pour avoir trois $a$ dans le mot au total), et
+finalement $w = b^p a b^q$ où $p,q>0$, et du coup $w a^n w = b^p a b^q
+a b^p a b^q$, qui est bien dans $M'$ comme annoncé.
+
+Sachant que $M' = L'\cap N$, puisque $N$ est rationnel par définition,
+et puisque $M'$ n'est pas algébrique comme il a été admis, le langage
+$L'$ n'est pas algébrique (l'intersection d'un langage algébrique et
+d'un langage rationnel étant algébrique, ainsi qu'il a été rappelé).
+
+\smallbreak
+
+(4a) Supposons par l'absurde que $M$ soit rationnel.  D'après le lemme
+de pompage, il existe un certain $k$ tel que tout mot $x$ de $M$ de
+longueur $\geq k$ se factorise sous la forme $x = uvw$ avec
+(i) $|v|\geq 1$, (ii) $|uv|\leq k$ et (iii) $uv^iw \in M$ pour
+tout $i\geq 0$.  Considérons le mot $x := b^k a b a b a b^k$, qui
+appartient à $M$ : il est censé exister une factorisation $x = uvw$
+comme on vient de le dire.  Mais d'après (ii), on voit que $u,v$ ne
+peuvent comporter que la lettre $b$ : disons $u = b^r$ et $v = b^s$,
+et donc $w = b^{k-r-s} a b a b a b^k$ ; la propriété (i) assure $s>0$,
+et on a $uv^iw = b^r b^{si} b^{k-r-s} a b a b a b^k = b^{k+s(i-1)} a b
+a b a b^k$, censé appartenir à $M$ pour tout $i$ d'après (iii).  Or
+dès que $i\neq 1$, ceci clairement une contradiction.  Le langage $M$
+n'est donc pas rationnel.
+
+(4b) De même qu'en (3), le langage $M$ est l'intersection du langage
+$L$ avec le langage rationnel $N$ (dénoté par l'expression rationnelle
+$b^{+} a b^{+} a b^{+} a b^{+}$) : soit $M = L\cap N$.  Mais puisque $N$
+est rationnel par définition, et puisque $M$ n'est pas rationnel comme
+il a été prouvé en (4a), le langage $L$ n'est pas rationnel
+(l'intersection de deux langages rationnels étant rationnelle).
+
+\smallbreak
+
+(5) On a vu en (4b) que $M = L\cap N$.  Comme $L$ est algébrique
+d'après (2), et que $N$ est rationnel, il en résulte que $M$ est
+algébrique (l'intersection d'un langage algébrique et d'un langage
+rationnel étant algébrique, ainsi qu'il a été rappelé).
+
+\smallbreak
+
+(6) On va expliquer comment écrire un algorithme qui décide si un mot
+$x$ de $\Sigma^*$ appartient à $L'$ : autrement dit, il s'agit de
+tester si $x$ peut s'écrire sous la forme $w a^n w$ pour un certain $w
+\in \Sigma^*$ et $n\in\mathbb{N}$.  Manifestement, si c'est le cas, la
+longueur $|w|$ de $w$ est majorée par $\frac{1}{2}|x|$ et qu'on a $n =
+|x| - 2|w|$, donc on peut procéder ainsi : pour chaque $k$ entier
+allant de $0$ à $\frac{1}{2}|x|$, et en appelant $n := |x|-2k$, tester
+si le préfixe de longueur $k$ de $x$ et son suffixe de longueur $k$
+sont égaux et si les $n$ lettres entre les positions $k$ incluse (en
+compsant à partir de $0$) et $k+n$ exclue sont toutes des $a$ : si
+oui, retourner vrai, et si la boucle se finit sans que la condition
+soit vérifiée, retourner faux.
+
+(De façon plus expéditive : comme la longueur de $w$ et la valeur de
+$n$ sont bornées, il n'y a qu'un nombre fini de possibilités à tester
+qui pourraient faire que $x = w a^n w$, donc quitte à tester tous les
+$w$ de longueur $\leq\frac{1}{2}|x|$ et tous les $n$ possibles jusqu'à
+$|x|$, on peut tester si on a $x = w a^n w$.)
+
+Comme $L'$ est décidable, en particulier, il est semi-décidable.
+
+\smallbreak
+
+(7) En se rappelant qu'un langage rationnel est algébrique, qu'un
+algébrique est décidable, et qu'un décidable est semi-décidable, et en
+ajoutant par ailleurs la colonne $N$ (qui n'était pas demandée), on a
+le tableau suivant :
+\begin{center}
+\begin{tabular}{r|ccccc}
+&$L$&$L'$&$M$&$M'$&$N$\\\hline
+rationnel ?&NON&NON&NON&NON&oui\\
+algébrique ?&oui&NON&oui&NON&oui\\
+décidable ?&oui&oui&oui&oui&oui\\
+semi-décidable ?&oui&oui&oui&oui&oui\\
+\end{tabular}
+\end{center}
+\vskip-\baselineskip\vskip-1ex\strut
+\end{corrige}
+
+
 
 %
 %
-- 
cgit v1.2.3