Intersection of algebraic and rational languages.

1 files changed, 38 insertions, 0 deletions

diff --git a/notes-inf105.tex b/notes-inf105.tex
index 84ff14d..b09ce0a 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -3184,6 +3184,29 @@ d'équations portant sur des langages (par exemple, la grammaire de
 définition des grammaires hors contexte revient à considérer la plus
 petite (au sens de l'inclusion) solution de ce système d'équations.
 
+\thingy À la différence des langages rationnels, il \emph{n'est pas
+  vrai} en général que l'intersection de deux langages algébriques
+soit algébrique : un contre-exemple est fourni par les deux langages
+$\{a^i b^i c^j : i,j\in\mathbb{N}\}$ et $\{a^i b^j c^j :
+i,j\in\mathbb{N}\}$ (chacun des deux est algébrique : par exemple, le
+premier est la concaténation du langage $\{a^i b^i : i\in\mathbb{N}\}$
+dont on a vu en \ref{basic-example-context-free-grammar} qu'il était
+algébrique, et du langage $\{c\}^*$, qui est algébrique car
+rationnel) ; leur intersection $\{a^i b^i c^i : i\in\mathbb{N}\}$
+n'est pas algébrique, comme on le démontrera
+en \ref{example-of-pumping-lemma-for-algebraic-languages}.
+
+En conséquence, il n'est pas non plus vrai en général que le
+complémentaire d'un langage algébrique soit algébrique.
+
+En revanche, le fait suivant, que nous admettons sans démonstration,
+peut s'avérer utile :
+
+\begin{prop}\label{intersection-of-algebraic-and-rational}
+L'intersection d'un langage \emph{algébrique} et d'un langage
+\emph{rationnel} est algébrique.
+\end{prop}
+
 
 \subsection{Autres exemples de grammaires hors contexte}
 
@@ -3715,6 +3738,21 @@ que le mot $t$ initial ; mais comme son nombre de $a$ ou bien de $b$
 est différent (d'après (i)), on a une contradiction.
 \end{proof}
 
+\thingy La proposition \ref{intersection-of-algebraic-and-rational}
+peut s'avérer utile pour montrer qu'un langage n'est pas algébrique.
+Par exemple, le langage $L$ formé des mots sur $\{a,b,c\}$ ayant le
+même nombre total de $a$, de $b$ et de $c$ (autrement dit $\{w \in
+\{a,b,c\}^* : |w|_a = |w|_b = |w|_c\}$ où $|w|_x$ désigne le nombre
+d'occurrences de la lettre $x$ dans le mot $w$) n'est pas algébrique :
+le plus simple pour le voir est de l'intersecter avec le langage
+rationnel $M := \{a^i b^j c^k : i,j,k\in\mathbb{N}\}$ (dénoté par
+l'expression rationnelle $a{*}b{*}c{*}$) : si $L$ était algébrique
+alors d'après \ref{intersection-of-algebraic-and-rational}, le langage
+$L\cap M$ le serait aussi ; mais $L\cap M = \{a^i b^i c^i :
+i\in\mathbb{N}\}$, et on vient de voir
+en \ref{example-of-pumping-lemma-for-algebraic-languages} qu'il n'est
+pas algébrique ; c'est donc que $L$ n'est pas non plus algébrique.
+
 
 
 %