Concatenation, union and star of CFLs.

1 files changed, 108 insertions, 20 deletions

diff --git a/notes-inf105.tex b/notes-inf105.tex
index d832a7e..ee28534 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -861,17 +861,18 @@ consommer.
   \textbf{fonction de transition}.
 \end{itemize}
 
-\thingy Graphiquement, on représente un DFA comme un graphe orienté
-aux arêtes étiquetées par des éléments de $\Sigma$ : plus exactement,
-on trace un nœud pour chaque élément $q \in Q$, et lorsque
-$\delta(q,x) = q'$ on introduit une flèche $q \to q'$ étiquetée par la
-lettre $x$.  La condition sur $\delta$ (pour être un DFA) est alors
-que, pour chaque état $q \in Q$ et chaque lettre $x \in \Sigma$, il
-existe une unique arête partant de $q$ et étiquetée par $x$.  En
-outre, on introduit une flèche pointant de nulle part vers $q_0$, et
-pour chaque $q\in F$ une flèche pointant de $q$ vers nulle
-part\footnote{Certains auteurs préfèrent d'autres conventions, par
-  exemple celle consistant à entourer deux fois les états finaux.}.
+\thingy\label{graphical-representation-of-dfa} Graphiquement, on
+représente un DFA comme un graphe orienté aux arêtes étiquetées par
+des éléments de $\Sigma$ : plus exactement, on trace un nœud pour
+chaque élément $q \in Q$, et lorsque $\delta(q,x) = q'$ on introduit
+une flèche $q \to q'$ étiquetée par la lettre $x$.  La condition sur
+$\delta$ (pour être un DFA) est alors que, pour chaque état $q \in Q$
+et chaque lettre $x \in \Sigma$, il existe une unique arête partant de
+$q$ et étiquetée par $x$.  En outre, on introduit une flèche pointant
+de nulle part vers $q_0$, et pour chaque $q\in F$ une flèche pointant
+de $q$ vers nulle part\footnote{Certains auteurs préfèrent d'autres
+  conventions, par exemple celle consistant à entourer deux fois les
+  états finaux.}.
 
 Lorsque plusieurs arêtes étiquetées par des lettres $x,y$ différentes
 relient les mêmes sommets $q,q'$ (i.e., lorsqu'on a à la fois
@@ -2836,7 +2837,7 @@ et les langages reconnus sont les mêmes.
 
 \section{Grammaires hors contexte}
 
-\subsection{Définition, notations, exemples}
+\subsection{Définition, notations et premier exemple}
 
 \thingy\label{definition-context-free-grammar} Une \textbf{grammaire
   hors contexte} (on dit parfois aussi « sans contexte » ; en anglais,
@@ -2933,7 +2934,7 @@ Concrètement, $\lambda \mathrel{\Rightarrow^*} \xi$ signifie donc
 qu'on peut passer de $\lambda$ à $\xi$ en effectuant une suite
 (finie !) de dérivations immédiates, c'est-à-dire en remplaçant à
 chaque étape un nonterminal $T$ par la partie droite $\alpha$ d'une
-règle $T \to \alpha$ de la grammaire $G$.
+règle $T \rightarrow \alpha$ de la grammaire $G$.
 
 Il va de soi qu'un pseudo-mot qui ne comporte que des terminaux, i.e.,
 qui est en fait un mot (sur $\Sigma$), ne peut pas être dérivé plus
@@ -2952,6 +2953,10 @@ Un langage qui peut s'écrire sous la forme $L(G)$ où $G$ est une
 grammaire hors contexte est appelé \textbf{langage hors contexte} ou
 \textbf{algébrique}.
 
+Deux grammaires hors contexte $G$ et $G'$ sont dites
+\textbf{faiblement équivalentes} ou \textbf{langage-équivalentes}
+lorsqu'elles engendrent le même langage ($L(G) = L(G')$).
+
 \thingy\label{basic-example-context-free-grammar} À titre d'exemple,
 considérons la grammaire sur l'alphabet $\Sigma = \{a,b\}$ donnée par
 \[
@@ -2988,8 +2993,11 @@ n\in\mathbb{N}\}$.
 
 On a vu en \ref{example-of-pumping-lemma} que ce langage n'est pas
 rationnel : il existe donc des langages algébriques qui ne sont pas
-rationnels.  En revanche, pour ce qui est de la réciproque, on a le
-fait suivant :
+rationnels.  En revanche, pour ce qui est de la réciproque, on verra
+dans la section suivante que tout langage rationnel est algébrique.
+
+
+\subsection{Langages rationnels et algébriques, stabilité}
 
 \begin{prop}\label{rational-languages-are-algebraic}
 Tout langage rationnel est algébrique.  Mieux, on peut déduire
@@ -3027,13 +3035,93 @@ t_n$ dérivé est précisément le mot formé en concacténant les
 \thingy Une grammaire hors contexte telle que construite dans la
 preuve de \ref{rational-languages-are-algebraic} est dite
 \textbf{régulière} : autrement dit, il s'agit d'une grammaire ayant
-uniquement des règles de la forme (A) $Q \to tQ'$ où $t \in
+uniquement des règles de la forme (A) $Q \rightarrow tQ'$ où $t \in
 \Sigma\cup\{\varepsilon\}$ (certains auteurs imposent $t \in \Sigma$,
 ce qui revient à imposer qu'on part d'un NFA sans ε-transition dans la
-construction) et (B) $Q \to \varepsilon$ (certains auteurs préfèrent
-$Q \to x$ avec $x\in\Sigma$, ce qui impose des petits changements dans
-la construction ci-dessus).  Les langages définis par des grammaires
-régulières sont donc exactement les langages rationnels.
+construction) et (B) $Q \rightarrow \varepsilon$ (certains auteurs
+préfèrent $Q \rightarrow x$ avec $x\in\Sigma$, ce qui impose des
+petits changements dans la construction ci-dessus).  Les langages
+définis par des grammaires régulières sont donc exactement les
+langages rationnels.
+
+\begin{prop}\label{cfg-union-concatenation-and-star}
+Si $L_1,L_2$ sont des langages algébriques (sur un même
+alphabet $\Sigma$), alors la réunion $L_1 \cup L_2$ est algébrique ;
+de plus, une grammaire hors contexte l'engendrant se déduit
+algorithmiquement de grammaires hors contexte engendrant $L_1$
+et $L_2$.
+
+Si $L_1,L_2$ sont des langages algébriques (sur un même
+alphabet $\Sigma$), alors la concaténation $L_1 L_2$ est algébrique ;
+de plus, une grammaire hors contexte l'engendrant se déduit
+algorithmiquement de grammaires hors contexte engendrant $L_1$
+et $L_2$.
+
+Si $L$ est un langage algébrique, alors l'étoile de Kleene $L^*$ est
+algébrique ; de plus, une grammaire hors contexte l'engendrant se
+déduit algorithmiquement d'une grammaire hors contexte engendrant $L$.
+\end{prop}
+\begin{proof}
+Pour la réunion : supposons que $G_1$ et $G_2$ engendrent $L_1$ et
+$L_2$ respectivement, et ont des ensembles de nonterminaux $N_1$ et
+$N_2$ disjoints, avec axiomes $S_1$ et $S_2$ respectivement.  On
+construit une grammaire $G$ dont l'ensemble des nonterminaux est $N_1
+\cup N_2 \cup \{S\}$ où $S$ est un nouveau nonterminal, choisi comme
+axiome, et les règles de production de $G$ sont celles de $G_1$,
+celles de $G_2$, et les deux règles supplémentaires $S \rightarrow
+S_1$ et $S \rightarrow S_2$.  Il est évident qu'une dérivation de $G$
+partant de $S$ est soit de la forme $S \Rightarrow S_1$ suivie d'une
+dérivation de $G_1$, soit de la forme $S \Rightarrow S_2$ suivie d'une
+dérivation de $G_2$ : ainsi, $L(G) = L_1 \cup L_2$.
+
+Pour la concaténation : la construction est presque exactement la
+même, mais on prend pour règle supplémentaire $S \rightarrow S_1 S_2$.
+
+Pour l'étoile : si $G$ engendre $L$ et a pour ensemble de nonterminaux
+$N$ et pour axiome $S$, on défit une nouvelle grammaire $G'$ dont
+l'ensemble des nonterminaux est $N' = N \cup \{S'\}$ où $S'$ est un
+nouveau nonterminal, choisi comme axiome, et les règles de production
+de $G'$ sont celles de $G$ et les deux règles supplémentaires $S'
+\rightarrow SS'$ et $S' \rightarrow \varepsilon$.  Il est facile de se
+convaincre qu'une dérivation de $G'$ partant de $S'$ et utilisant $n$
+fois la règle $S' \rightarrow SS'$ se ramène à $n$ dérivations de $G$
+partant de $S$, et seule la règle $S' \rightarrow \varepsilon$ permet
+de faire disparaître le symbole $S'$.  (Les détails sont omis et
+peuvent être rendus plus clairs en utilisant la notion d'arbre de
+dérivation.)
+\end{proof}
+
+\thingy Ceci fournit une nouvelle démonstration (partant d'une
+expression rationnelle plutôt que d'un automate)
+de \ref{rational-languages-are-algebraic}, tant il est évident que les
+langages $\varnothing$, $\{\varepsilon\}$ et $\{x\}$
+(pour $x\in\Sigma$) sont algébriques.
+
+À cause de cette construction, on se permettra parfois, dans l'énoncé
+des règles d'une grammaire, d'écrire $T \rightarrow \alpha_1 | \cdots
+| \alpha_n$ pour réunir en une seule ligne plusieurs règles $T
+\rightarrow \alpha_1$ jusqu'à $T \rightarrow \alpha_n$.  Par exemple,
+la grammaire présentée en \ref{basic-example-context-free-grammar}
+peut s'écrire $S \rightarrow aSb | \varepsilon$.  Il s'agit d'un
+simple racourci d'écriture (comparer avec une convention semblable
+faite pour les automates en \ref{graphical-representation-of-dfa}).
+
+On pourrait même se permettre l'abus de notation consistant à écrire
+$T \rightarrow U^*$ pour $T \rightarrow UT|\varepsilon$ (c'est-à-dire
+$T \rightarrow UT$ et $T \rightarrow \varepsilon$), mais il vaut mieux
+éviter car cela pourrait aussi bien signifier $T \rightarrow
+TU|\varepsilon$, qui engendre le même langage (i.e., elle est
+faiblement équivalente à la précédente) mais dont l'analyse peut être
+plus problématique.  De façon encore plus générale, on pourrait
+imaginer d'autoriser des règles de la forme $T \rightarrow r$ où $T$
+est un nonterminal et $r$ une expression rationnelle quelconque sur
+l'alphabet $\Sigma \cup N$ : de telles règles pourraient se ramener
+aux règles qu'on a autorisées, quitte à introduire de nouveaux
+nonterminaux pour les expressions intermédiaires (par exemple, $T
+\rightarrow UV^*$ se transformerait par l'introduction d'un nouveau
+nonterminal $V'$ en $T \rightarrow UV'$ et $V' \rightarrow
+VV'|\varepsilon$).  Nous éviterons ces extensions aux grammaires hors
+contexte pour ne pas introduire de confusion.