<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">
\thispagestyle{empty}
\vskip 20pt
Dans ce paragraphe, nous prÃ©cisons les Ã©lÃ©ments sur les grammaires et sur les langages qui ont dÃ©jÃ&nbsp; Ã©tÃ© vus jusqu'Ã&nbsp; prÃ©sent.

\section{Langages}

\begin{Notation}
Soit $\Sigma$ un ensemble de symboles, on note par $\Sigma^*$ l'ensemble des mots sur $\Sigma$, c'est-Ã&nbsp;-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 Ã&nbsp; 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 ($&lt;expression&gt; ::= ...$).
\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 Ã&nbsp; plusieurs bandes.

\index{langages!rÃ©cursivement Ã©numÃ©rables}
\index{machines!de Turing!non dÃ©terministes Ã&nbsp; 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-Ã&nbsp;-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 Ã&nbsp; 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Ã© Ã&nbsp; une grammaire}

RÃ©ciproquement, le langage peut Ãªtre considÃ©rÃ© comme langage associÃ© Ã&nbsp; la grammaire $G$, $\mathcal{L}(G)$.

\section{Un exemple de grammaire contextuelle}

Nous n'avons jusqu'Ã&nbsp; prÃ©sent considÃ©rÃ© que des grammaires de type au moins 2, puisque toutes nos rÃ¨gles de grammaire (Ã©crites jusqu'Ã&nbsp; 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 Ã&nbsp; 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$ Ã&nbsp; 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 Ã&nbsp; des Ã©checs, en raison du non-dÃ©terminisme de la grammaire).



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

</pre></body></html>