automates/DescriptionLangageParGrammaire.tex

   1
   2 \thispagestyle{empty}
   3 \vskip 20pt
   4 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.
   5
   6 \section{Langages}
   7
   8 \begin{Notation}
   9 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$.
  10 \end{Notation}
  11
  12
  13 \begin{Th}
  14 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$.\\
  15 \end{Th}
  16
  17 \begin{Def}[Langage sur $\Sigma$]
  18 \index{langage}
  19 On appelle \emph{langage} sur $\Sigma$ toute partie de $\Sigma^*$.\\
  20 \end{Def}
  21
  22
  23 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.
  24
  25
  26 Nous nous limiterons ici aux grammaires de Chomsky.
  27
  28
  29
  30 \section{Grammaires}
  31
  32 \subsection{Définitions}
  33
  34 \begin{Def}[Grammaire de Chomsky]
  35 Une \emph{grammaire de Chomsky}\index{grammaire!de Chomsky} est un quadruplet $G = (\Sigma, N, P, S)$, où
  36 \begin{itemize}
  37 \item $\Sigma$ est un ensemble fini, appelé \emph{alphabet du langage}\index{langage!alphabet}, ou ensemble des symboles terminaux du langage,
  38 \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,
  39 \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,
  40 \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> ::= ...$).
  41 \end{itemize}
  42 \end{Def}
  43
  44
  45 Les éléments de $P$ sont aussi appelés \emph{productions} \index{productions}.
  46
  47 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)^*$.
  48
  49 \begin{Notation}
  50 Une telle production est le plus souvent notée $\alpha \rightarrow \beta$, qui se lit \og $\alpha$ se réécrit en $\beta$\fg{}.
  51 \end{Notation}
  52
  53
  54 \begin{Rem}
  55 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{} ).
  56 \end{Rem}
  57
  58 \subsection{Types de grammaires de Chomsky}
  59
  60 On distingue divers types de grammaires de Chomsky :
  61
  62
  63 \subsubsection{Les grammaires non restreintes, ou de type 0}
  64 \index{grammaire!non restreinte}
  65 \index{grammaire!de type 0}
  66 Aucune restriction n'est apportée aux productions.
  67
  68 Les langages sont dits récursivement énumérables. Ils sont reconnus par des machines de Turing non déterministes à plusieurs bandes.
  69
  70 \index{langages!récursivement énumérables}
  71 \index{machines!de Turing!non déterministes à plusieurs bandes}
  72
  73 \subsubsection{Les grammaires contextuelles, ou de type 1}
  74 \index{grammaire!contextuelle}
  75 \index{grammaire!de type 1}
  76
  77 Les langages correspondants sont les langages contextuels.
  78
  79 Ceux-ci constituent un sous-ensemble des langages récursifs (c'est-à-dire récursivement énumérables ainsi que leur complémentaire).
  80
  81 Ils sont reconnus par des machines de Turing déterministes.
  82
  83 \index{langages!contextuels}
  84 \index{machines!de Turing!déterministes}
  85
  86 \subsubsection{Les grammaires algébriques, ou de type 2}
  87
  88 \index{grammaire!algébrique}
  89 \index{grammaire!de type 2}
  90
  91 Toute production est de la forme $A \rightarrow \alpha$, où $A \in N$ et $\alpha \in ( \Sigma \cup N)^*$.
  92
  93 Il y a équivalence entre les langages reconnaissables par des automates à pile et les langages algébriques (engendrés par une grammaire algébrique).
  94
  95 \index{langages!algébrique}
  96
  97 \subsubsection{Les grammaires régulières, ou de type 3}
  98
  99 \index{grammaire!régulière}
 100 \index{grammaire!de type 3}
 101
 102
 103 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^*$.
 104
 105 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).
 106
 107 \index{langages!reconnaissables par des automates finis}
 108 \index{langages!réguliers}
 109
 110 \subsubsection{Langage associé à une grammaire}
 111
 112 Réciproquement, le langage peut être considéré comme langage associé à la grammaire $G$, $\mathcal{L}(G)$.
 113
 114 \section{Un exemple de grammaire contextuelle}
 115
 116 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.\\
 117
 118 \begin{Ex}[Grammaire contextuelle]
 119 Voici un exemple de grammaire contextuelle : celle qui permet de définir le langage $\{ a^n b^n c^n | n \in \mathbb{N}^* \}$.
 120
 121 \begin{enumerate}
 122  \item $S \rightarrow aSBC$
 123  \item $S \rightarrow aBC$
 124  \item $CB \rightarrow BC$
 125  \item $aB \rightarrow ab$
 126  \item $bB \rightarrow bb$
 127  \item $bC \rightarrow bc$
 128  \item $cC \rightarrow cc$
 129 \end{enumerate}
 130 \end{Ex}
 131
 132
 133 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.
 134
 135 \begin{Ex}
 136 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.
 137 \end{Ex}
 138
 139
 140 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).
 141
 142 \begin{itemize}
 143  \item Il faut dériver $S$
 144  \item $S$ se dérive en $aSBC$ (règle 1)
 145  \item $S$ se dérive en $aSBC$ (règle 1), donc $aSBC$ en $aaSBCBC$
 146  \item $CB$ se dérive en $BC$ (règle 3), donc $aaSBCBC$ en $aaSBBCC$
 147  \item $S$ se dérive en $aBC$ (règle 2), donc $aaSBBCC$ en $aaaBCBBCC$
 148 \item $CB$ se dérive en $BC$ (règle 3), donc $aaaBCBBCC$ en $aaaBBCBC$
 149 \item $CB$ se dérive en $BC$ (règle 3), donc $aaaBBCBCC$ en $aaaBBBCCC$
 150 \item $aB$ se dérive en $ab$ (règle 4), donc $aaaBBBCCC$ en $aaabBBCCC$
 151 \item $bB$ se dérive en $bb$ (règle 5), donc $aaabBBCCC$ en $aaabbBCCC$
 152 \item $bB$ se dérive en $bb$ (règle 5), donc $aaabbBCCC$ en $aaabbbCCC$
 153 \item $bC$ se dérive en $bc$ (règle 6), donc $aaabbbCCC$ en $aaabbbcCC$
 154 \item $cC$ se dérive en $cc$ (règle 7), donc $aaabbbcCC$ en $aaabbbccC$
 155 \item $cC$ se dérive en $cc$ (règle 7), donc $aaabbbccC$ en $aaabbbccc$
 156 \end{itemize}
 157
 158 \bigskip
 159
 160 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).
 161
 162
 163
 164 \gsaut
 165 \centerline{\x{Fin du Chapitre}}
 166