diff options
Diffstat (limited to 'notes-inf105.tex')
| -rw-r--r-- | notes-inf105.tex | 38 |
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. + % |