summaryrefslogtreecommitdiffstats
path: root/notes-inf105.tex
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2017-01-02 15:37:17 +0100
committerDavid A. Madore <david+git@madore.org>2017-01-02 15:37:17 +0100
commit92bc06542694541eec720be661a08d2a1fa6f04a (patch)
tree25cdd15393b9c9f87921b1ba7f971b70c3f422e8 /notes-inf105.tex
parentfb03b072ff55ef36cd244285e46ebb51db715cec (diff)
downloadinf105-92bc06542694541eec720be661a08d2a1fa6f04a.tar.gz
inf105-92bc06542694541eec720be661a08d2a1fa6f04a.tar.bz2
inf105-92bc06542694541eec720be661a08d2a1fa6f04a.zip
Concatenation, union and star of CFLs.
Diffstat (limited to 'notes-inf105.tex')
-rw-r--r--notes-inf105.tex128
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.