diff options
| -rw-r--r-- | notes-inf105.tex | 128 |
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. |