
\thispagestyle{empty}
\vskip 20pt
Dans ce paragraphe, nous précisons les éléments sur les grammaires et sur les langages qui ont déjà été vus jusqu'à présent.

\section{Langages}

\begin{Notation}
Soit $\Sigma$ un ensemble de symboles, on note par $\Sigma^*$ l'ensemble des mots sur $\Sigma$, c'est-à-dire l'ensemble des assemblages de symboles de $\Sigma$.
\end{Notation}


\begin{Th}
Pour l'opération de concaténation des assemblages de symboles, $\Sigma^*$ constitue un monoïde (opération associative, admettant un élément neutre, la chaîne vide, notée $\varepsilon$) appelé \emph{monoïde libre sur}\index{monoïde libre} $\Sigma$.\\
\end{Th}

\begin{Def}[Langage sur $\Sigma$]
\index{langage}
On appelle \emph{langage} sur $\Sigma$ toute partie de $\Sigma^*$.\\
\end{Def}


Tout le problème consiste à se donner les moyens de définir un langage. L'un d'entre eux est de se donner un système générateur de ce langage, qu'on appelle grammaire.


Nous nous limiterons ici aux grammaires de Chomsky.



\section{Grammaires}

\subsection{Définitions}

\begin{Def}[Grammaire de Chomsky]
Une \emph{grammaire de Chomsky}\index{grammaire!de Chomsky} est un quadruplet $G = (\Sigma, N, P, S)$, où
\begin{itemize}
\item $\Sigma$ est un ensemble fini, appelé \emph{alphabet du langage}\index{langage!alphabet}, ou ensemble des symboles terminaux du langage,
\item $N$ est un autre ensemble fini, disjoint de $\Sigma$, et appelé ensemble des symboles non-terminaux, qui constituent un méta-langage dans lequel sera décrit le langage,
\item $P$ est une partie finie de $((\Sigma \cup N)^* \setminus \Sigma^*) \times (\Sigma \cup N)^*)$ : c'est l'ensemble des règles de la grammaire,
\item $S$ est un élément de $N$ (un symbole non-terminal), \emph{symbole initial} ou \emph{axiome}\index{grammaire!axiome} de la grammaire ($<expression> ::= ...$).
\end{itemize}
\end{Def}


Les éléments de $P$ sont aussi appelés \emph{productions} \index{productions}.

Ce sont des couples de suites de symboles, la première de ces deux suites comportant au moins un symbole non-terminal. Elles sont de la forme ($\alpha, \beta$), où $\alpha \in ( \Sigma \cup N)^*$, mais $\alpha \notin \Sigma^*$ et $\beta \in ( \Sigma \cup N)^*$.

\begin{Notation}
Une telle production est le plus souvent notée $\alpha \rightarrow \beta$, qui se lit \og $\alpha$ se réécrit en $\beta$\fg{}.
\end{Notation}


\begin{Rem}
La flèche n'est pas ici le symbole de l'implication logique, mais celui de réécriture (dans la symbolisation BNF, ou Bakus-Naur form, le symbole de réécriture est \og ::=\fg{} ).
\end{Rem}

\subsection{Types de grammaires de Chomsky}

On distingue divers types de grammaires de Chomsky :


\subsubsection{Les grammaires non restreintes, ou de type 0}
\index{grammaire!non restreinte}
\index{grammaire!de type 0}
Aucune restriction n'est apportée aux productions.

Les langages sont dits récursivement énumérables. Ils sont reconnus par des machines de Turing non déterministes à plusieurs bandes.

\index{langages!récursivement énumérables}
\index{machines!de Turing!non déterministes à plusieurs bandes}

\subsubsection{Les grammaires contextuelles, ou de type 1}
\index{grammaire!contextuelle}
\index{grammaire!de type 1}

Les langages correspondants sont les langages contextuels.

Ceux-ci constituent un sous-ensemble des langages récursifs (c'est-à-dire récursivement énumérables ainsi que leur complémentaire).

Ils sont reconnus par des machines de Turing déterministes.

\index{langages!contextuels}
\index{machines!de Turing!déterministes}

\subsubsection{Les grammaires algébriques, ou de type 2}

\index{grammaire!algébrique}
\index{grammaire!de type 2}

Toute production est de la forme $A \rightarrow \alpha$, où $A \in N$ et $\alpha \in ( \Sigma \cup N)^*$.

Il y a équivalence entre les langages reconnaissables par des automates à pile et les langages algébriques (engendrés par une grammaire algébrique).

\index{langages!algébrique}

\subsubsection{Les grammaires régulières, ou de type 3}

\index{grammaire!régulière}
\index{grammaire!de type 3}


Chaque production est de l'une des formes $A \rightarrow xB$ ou $A \rightarrow x$, avec $(A,B) \in N^2$ et $x \in \Sigma^*$.

Il y a équivalence entre les langages reconnaissables par des automates finis et les langages réguliers (certains disent \og rationnels\fg{}  ; engendrés par une grammaire régulière).

\index{langages!reconnaissables par des automates finis}
\index{langages!réguliers}

\subsubsection{Langage associé à une grammaire}

Réciproquement, le langage peut être considéré comme langage associé à la grammaire $G$, $\mathcal{L}(G)$.

\section{Un exemple de grammaire contextuelle}

Nous n'avons jusqu'à présent considéré que des grammaires de type au moins 2, puisque toutes nos règles de grammaire (écrites jusqu'à présent en symbolisme BNF) ont toujours consisté en la définition d'un symbole non-terminal.\\

\begin{Ex}[Grammaire contextuelle]
Voici un exemple de grammaire contextuelle : celle qui permet de définir le langage $\{ a^n b^n c^n | n \in \mathbb{N}^* \}$.

\begin{enumerate}
 \item $S \rightarrow aSBC$
 \item $S \rightarrow aBC$
 \item $CB \rightarrow BC$
 \item $aB \rightarrow ab$
 \item $bB \rightarrow bb$
 \item $bC \rightarrow bc$
 \item $cC \rightarrow cc$
\end{enumerate}
\end{Ex}


Ces grammaires sont appelées \og contextuelles\fg{} parce qu'il est impossible de donner une définition \og indépendante\fg{}  de chacun des SNT, comme dans les grammaires algébriques.

\begin{Ex}
On ne peut, par exemple dans la grammaire ci-dessus, pas donner de définition du SNT $B$ indépendamment des symboles qui l'entourent, donc la définition de $B$ est sensible au contexte et la grammaire dans laquelle elle figure est dite contextuelle.
\end{Ex}


Pour se convaincre de la validité de cet exemple de grammaire, voici l'analyse de la chaîne correcte $aaabbbccc$ en utilisant les règles (ce que l'on appelle une dérivation de chaîne relativement à la grammaire).

\begin{itemize}
 \item Il faut dériver $S$
 \item $S$ se dérive en $aSBC$ (règle 1)
 \item $S$ se dérive en $aSBC$ (règle 1), donc $aSBC$ en $aaSBCBC$
 \item $CB$ se dérive en $BC$ (règle 3), donc $aaSBCBC$ en $aaSBBCC$
 \item $S$ se dérive en $aBC$ (règle 2), donc $aaSBBCC$ en $aaaBCBBCC$
\item $CB$ se dérive en $BC$ (règle 3), donc $aaaBCBBCC$ en $aaaBBCBC$
\item $CB$ se dérive en $BC$ (règle 3), donc $aaaBBCBCC$ en $aaaBBBCCC$
\item $aB$ se dérive en $ab$ (règle 4), donc $aaaBBBCCC$ en $aaabBBCCC$
\item $bB$ se dérive en $bb$ (règle 5), donc $aaabBBCCC$ en $aaabbBCCC$
\item $bB$ se dérive en $bb$ (règle 5), donc $aaabbBCCC$ en $aaabbbCCC$
\item $bC$ se dérive en $bc$ (règle 6), donc $aaabbbCCC$ en $aaabbbcCC$
\item $cC$ se dérive en $cc$ (règle 7), donc $aaabbbcCC$ en $aaabbbccC$
\item $cC$ se dérive en $cc$ (règle 7), donc $aaabbbccC$ en $aaabbbccc$
\end{itemize}

\bigskip

La dérivation de $aaabbbccc$ à partir de $S$ est couronnée de succès, l'expression est correct (on n'a pas fait figurer les tentatives d'application de règles qui aboutissent à des échecs, en raison du non-déterminisme de la grammaire).



\gsaut
\centerline{\x{Fin du Chapitre}}

