summaryrefslogtreecommitdiffstats
path: root/notes-inf105.tex
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2017-01-10 14:33:02 (GMT)
committerDavid A. Madore <david+git@madore.org>2017-01-10 14:33:02 (GMT)
commitf2f2d800f44cee4f6e56494a597ba96e82114212 (patch)
tree77a8b648217bb8b899252c6862b85a68d4518284 /notes-inf105.tex
parent87df1b27a05d9192093b5d14a32da1dacc1a0d42 (diff)
downloadinf105-f2f2d800f44cee4f6e56494a597ba96e82114212.zip
inf105-f2f2d800f44cee4f6e56494a597ba96e82114212.tar.gz
inf105-f2f2d800f44cee4f6e56494a597ba96e82114212.tar.bz2
Intersection of algebraic and rational languages.
Diffstat (limited to 'notes-inf105.tex')
-rw-r--r--notes-inf105.tex38
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.
+
%