diff options
| -rw-r--r-- | notes-inf105.tex | 138 |
1 files changed, 136 insertions, 2 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex index af3404b..b87818d 100644 --- a/notes-inf105.tex +++ b/notes-inf105.tex @@ -3123,13 +3123,125 @@ 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. +\thingy Il peut être utile, pour raisonner sur les langages +algébriques, d'introduire, lorsque $G$ est une grammaire hors contexte +et $T$ un nonterminal quelconque, le langage $L(G,T)$ des mots qui +dérivent de $T$, c'est-à-dire le langage engendré par la grammaire +$G'$ identique à $G$ à ceci près que son axiome est $T$. + +On a alors $L(G) = L(G,S)$ où $S$ est l'axiome de $G$, et chaque règle +de production $T \rightarrow \alpha_1 | \cdots | \alpha_n$ se traduit +par une équation portant sur $L(G,T)$, par exemple $T \rightarrow aUbV +| cW$ implique $L(G,T) = a\, L(G,U)\, b\, L(G,V) \; \cup \; c L(G,W)$. +De cette manière, une grammaire hors contexte donne lieu à un système +d'équations portant sur des langages (par exemple, la grammaire de +\ref{basic-example-context-free-grammar} donne lieu à l'équation $L(G) += (a\,L(G)\,b) \cup \{\varepsilon\}$ : on peut montrer que la +définition des grammaires hors contexte revient à considérer la plus +petite (au sens de l'inclusion) solution de ce système d'équations. + \subsection{Autres exemples de grammaires hors contexte} +\thingy Sur l'alphabet $\Sigma = \{a,b\}$, considérons la grammaire +(d'axiome $S$) +\[ +\begin{aligned} +S &\rightarrow AT\\ +A &\rightarrow aA \;|\; \varepsilon\\ +T &\rightarrow aTb \;|\; \varepsilon\\ +\end{aligned} +\] +Il est clair que le langage $L(G,A)$ des mots qui dérivent de $A$ est +simplement $\{a\}^* = \{a^i : i\in\mathbb{N}\}$ ; et le langage +$L(G,T)$ est $\{a^j b^j : j\in\mathbb{N}\}$ comme +en \ref{basic-example-context-free-grammar}. Le langage $L(G) = +L(G,A)\, L(G,T)$ est donc $\{a^i b^j : i \geq j\}$, l'ensemble des +mots de la forme $a^i b^j$ pour lesquels $i \geq j$. (Ce langage est +intéressant sur le plan théorique, car bien qu'il soit algébrique et +ici défini par une grammaire inambiguë, il ne peut pas être analysé +par un analyseur LL.) + +On peut aussi considérer la grammaire $G'$ définie par +\[ +\begin{aligned} +S &\rightarrow T \;|\; aS\\ +T &\rightarrow aTb \;|\; \varepsilon\\ +\end{aligned} +\] +Il n'est pas difficile de se convaincre qu'elle engendre le même +langage $L(G)$ que la précédente (elle est donc faiblement équivalente +à $G$). + +\thingy Sur l'alphabet $\Sigma = \{a,b\}$, considérons la grammaire +(d'axiome $S$) +\[ +\begin{aligned} +S &\rightarrow U \;|\; V \;|\; \varepsilon\\ +U &\rightarrow aUb \;|\; ab\\ +V &\rightarrow aVbb \;|\; abb\\ +\end{aligned} +\] +Il est clair que le langage $L(G,U)$ des mots qui dérivent de $U$ est +$\{a^i b^i : i>0\}$ comme en \ref{basic-example-context-free-grammar}, +et de façon analogue, le langage $L(G,V)$ des mots qui dérivent de $V$ +est $\{a^i b^{2i} : i>0\}$. Le langage $L(G) = L(G,U) \cup L(G,V)$ +est donc l'ensemble des mots de la forme $a^i b^j$ où $j=i$ \emph{ou + bien} $j=2i$. (Ce langage est intéressant sur le plan théorique, +car bien qu'il soit algébrique et défini par une grammaire inambiguë, +il n'est pas analysable par un automate à pile déterministe.) + +\thingy Sur l'alphabet $\Sigma = \{a,b,c\}$, considérons la grammaire +(d'axiome $S$) +\[ +\begin{aligned} +S &\rightarrow UC \;|\; AV\\ +A &\rightarrow aA \;|\; \varepsilon\\ +C &\rightarrow cC \;|\; \varepsilon\\ +U &\rightarrow aUb \;|\; \varepsilon\\ +V &\rightarrow bVc \;|\; \varepsilon\\ +\end{aligned} +\] +Il est clair que le langage $L(G,A)$ des mots qui dérivent de $A$ est +simplement $\{a\}^* = \{a^i : i\in\mathbb{N}\}$ et que le langage +$L(G,C)$ des mots qui dérivent de $C$ est simplement $\{c\}^* = \{c^j +: j\in\mathbb{N}\}$ ; le langage $L(G,U)$ est $\{a^i b^i : +i\in\mathbb{N}\}$ comme en \ref{basic-example-context-free-grammar}, +et de même $L(G,V) = \{b^j c^j : j\in\mathbb{N}\}$. Finalement, $L(G) += L(G,U)\,L(G,C) \;\cup\; L(G,A)\,L(G,V)$ montre que $L(G) = \{a^i b^i +c^j : i,j\in\mathbb{N}\} \cup \{a^i b^j c^j : i,j\in\mathbb{N}\}$ est +le langage des mots de la forme $a^i b^r c^j$ où $r=i$ \emph{ou} +$r=j$. (Ce langage est intéressant sur le plan théorique, car il est +algébrique mais « intrinsèquement ambigu ».) + +\thingy Sur l'alphabet $\Sigma = \{a,b\}$, considérons la grammaire +(d'axiome $S$) +\[ +S\; \rightarrow\; aSbS \;|\; \varepsilon +\] +ou, ce qui revient au même +\[ +\begin{aligned} +S &\rightarrow TS \;|\; \varepsilon\\ +T &\rightarrow aSb\\ +\end{aligned} +\] +(la première ligne revient par ailleurs à $S \rightarrow T^*$). On a +alors $L(G) = L(G,T)^*$ où $L(G,T) = a\, L(G)\, b$ désigne le langage +des mots qui peuvent être dérivés à partir de $T$. + +Ce langage $L(G)$ s'appelle langage des \textbf{expressions + bien-parenthésées} où $a$ représente une parenthèse ouvrante et $b$ +une parenthèse fermante (et $L(G,T)$ est le langage des blocs +parenthésés : autrement dit, une expression bien-parenthésée est une +suite de blocs parenthésés, et un bloc parenthésé est une expression +bien-parenthésée entourée par une parenthèse ouvrante et une +parenthèse fermante — c'est ce que traduit la grammaire). + \thingy Sur l'alphabet $\Sigma = \{a,b\}$, montrons que la grammaire -$G$ donnée par +$G$ (d'axiome $S$) donnée par \[ -S\; \rightarrow\;\; aSbS \;|\; bSaS \;|\; \varepsilon +S\; \rightarrow\; aSbS \;|\; bSaS \;|\; \varepsilon \] (c'est-à-dire $N = \{S\}$ où $S$ est l'axiome, et pour règles $S \rightarrow aSbS$ et $S \rightarrow bSaS$ et $S \rightarrow @@ -3167,6 +3279,28 @@ appartiennent à $L(G)$. On peut donc dériver $u$ et $v$ de $S$, donc $w$ de $aSbS$, et comme $aSbS$ se dérive immédiatement de $S$, on a bien $w \in L(G)$, ce qui conclut la récurrence. +Un raisonnement analogue montre que la grammaire $G'$ donnée par +\[ +\begin{aligned} +S &\rightarrow aUbS \;|\; bVaS \;|\; \varepsilon\\ +U &\rightarrow aUbU\\ +V &\rightarrow bVaV\\ +\end{aligned} +\] +engendre le même langage $L = \{w \in\Sigma^* : |w|_a = |w|_b\}$ que +ci-dessus (elle est donc faiblement équivalente à $G$) : l'idée est +que le langage $L(G,U)$ des mots qui dérivent de $U$ est l'ensemble +des expressions bien-parenthésées où $a$ est la parenthèse ouvrante et +$b$ la fermante (dans le raisonnement ci-dessus, ce sont les mots pour +lesquels la fonction $h$, partant de $0$, revient à $0$, et reste +toujours positive ou nulle), tandis que $L(G,V)$ est l'ensemble des +expressions bien-parenthésées où $b$ est la parenthèse ouvrante et $a$ +la fermante (la fonction $h$ reste toujours négative ou nulle), et +tout mot de $L$ peut s'écrire comme concaténation de tels mots (en +divisant selon le signe de $h$). Une différence entre $G$ et $G'$ est +que la grammaire $G$ est ambiguë (un terme qui sera défini plus bas) +tandis que $G'$ ne l'est pas. + % |