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.
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$.
Théorème
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é monoïde libre sur $\Sigma$.
Définition (Langage sur $\Sigma$)
On appelle langage sur $\Sigma$ toute partie de $\Sigma^*$.
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.
Définition (Grammaire de Chomsky)
Une grammaire de Chomsky est un quadruplet $G = (\Sigma, N, P, S)$, où
Les éléments de $P$ sont aussi appelés 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)^*$.
Notation: Une telle production est le plus souvent notée $\alpha \rightarrow \beta$, qui se lit « $\alpha$ se réécrit en $\beta$».
Remarque : 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 « ::=» ).
On distingue divers types de grammaires de Chomsky :
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.
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.
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).
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 « rationnels» ; engendrés par une grammaire régulière).
Réciproquement, le langage peut être considéré comme langage associé à la grammaire $G$, $\mathcal{L}(G)$.
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.
Exemple : [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}^* \}$.
Ces grammaires sont appelées « contextuelles» parce qu'il est impossible de donner une définition « indépendante» de chacun des SNT, comme dans les grammaires algébriques.
Exemple : 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.
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).
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).