Grammaires et hiérarchie de Chomsky
Terminaux, non-terminaux, axiome et règles de production ; le langage qu'une grammaire engendre ; les quatre types de Chomsky avec la forme de leurs règles, leur machine et un langage témoin.
- 28 cartes
- 3 thèmes
- Gratuit
Le programme, thème par thème
Le poids de chaque thème suit celui que lui donne l'examen.
- Notions
- Questions
- Ranger et relier
Quelques cartes du deck
Grammaire formelle : de quoi s'agit-il ?
Voir la réponse
Quadruplet formé d'un ensemble de terminaux, d'un ensemble de non-terminaux, d'un symbole de départ (l'axiome) et de règles de production qui réécrivent des suites de symboles.
Les mots du langage engendré sont ceux qu'on obtient en réécrivant l'axiome jusqu'à ne plus avoir que des terminaux.
Quel est le type de Chomsky le plus précis de la grammaire S → aSb | ε ?
- Type 2, hors contexte
- Type 3, régulier
- Type 1, contextuel
- Type 0, général
Voir la réponse
Type 2, hors contexte
Chaque règle a un seul non-terminal à gauche, mais aSb a le non-terminal au milieu : ce n'est pas la forme du type 3. Le langage engendré, aⁿbⁿ, n'est d'ailleurs pas régulier. Les types 1 et 0 contiennent le type 2 mais sont moins précis.
Une grammaire se donne par des … (les lettres des mots), des … (les symboles à réécrire), un … et des règles de production.
Voir la réponse
Une grammaire se donne par des terminaux (les lettres des mots), des non-terminaux (les symboles à réécrire), un axiome et des règles de production.
Dans S → aSb | ab, S est le seul non-terminal et l'axiome ; a et b sont les terminaux. Un mot du langage ne contient que des terminaux.
Hiérarchie de Chomsky : de quoi s'agit-il ?
Voir la réponse
Classement des grammaires en quatre types emboîtés, de 3 (le plus restreint) à 0 (le plus général), selon la forme permise pour leurs règles.
Plus le numéro du type est grand, plus la machine qui reconnaît le langage est simple, mais moins le langage peut être riche : type 3 ⊂ type 2 ⊂ type 1 ⊂ type 0.
Laquelle de ces règles interdit à une grammaire d'être de type 3 ?
- S → aS
- S → aSb
- A → bA
- S → b
Voir la réponse
S → aSb
En type 3, un seul non-terminal peut figurer à droite et seulement en dernière position. Dans aSb, il est suivi d'un terminal : il faudrait empiler le a pour s'en souvenir, ce que ne fait pas un automate fini.