Les langages formels
La théorie des langages formels fut initialement initiée par les linguistes qui tentaient de représenter les langages naturels (exemple, français, anglais, etc). Mais elle s'est révélée être très utile pour l'informatique pour tout un cas d'applications. Notamment les RegEx, et les règles syntaxiques des langages de programmations (avec l'analyse syntaxique).
Un langage naturel va être défini par une orthographe, une grammaire, une conjugaison. Un langage dit formel (tel que les langages de programmations), vont être défini par des règles de constructions. Ainsi, les erreurs syntaxiques d'un code peuvent être détectées grâce à ces mêmes règles de constructions.
La théorie des langages a pour but de décrire les langages formels. Elle ne concerne que les aspects purement syntaxiques du langage. Un langage formel est généralement défini par une grammaire formelle (grammaires algébriques, par exemple) et analysé à l’aide d’automates.
Donc un langage formel va être généré à l'aide d'une grammaire formelle et analysé à l'aide d'un automate.
Alphabets, lettres et mots
L'alphabet est un ensemble fini et non-vide d'éléments appelé lettres ou symboles terminaux. Cet ensemble va être représenté par la lettre
correspond à l'ensemble de tous les mots sur correspond à l'ensemble de tous les mots non-vide sur
Un mot est une séquence finie de lettres. Ainsi dans l'alphabet précédent a
, ab
et else
sont des mots par exemples.
Le mot vide est noté
Opérations
La concaténation est une opération binaire effectuée sur l'ensemble
Une concaténation des mots
Un exposant
Ainsi ab
est présente une fois ou plus. Et vb
est présente 0 fois ou plus.
Une autre opération est qu'un mot peut être retourné en lui mettant un exposant de -1
. Donc
Et on peut aussi récupérer la longueur d'un mot (nombre de symboles terminaux/lettres) comme ceci
Langage
Un langage est un sous ensemble de
est le langage de tous les mots de longueur 1 sur est un langage ne contenant aucun mot- {
} est un langage ne contenant que le mot vide langage contenant tous les mots sur langage contenant tous les mots sur
Sur l'ensemble
Aisni si
On peut utiliser la notation
Pour décrire un langage avec une infinité de mots, on peut utiliser un système générateur (grammaire, RegEx ou diagramme syntaxique) pour générer des mots du langage et des automates finis pour les détecter.
Pour la concaténation de 2 langages, les exposants
Quand on applique acbcb
car cela correspond à
Grammaire
Ici, on va examiner les grammaires dites "de Chomsky" qui représente la forme la plus connue de système de génération de langages, qui sont définies par le quadruplet
est la grammaire est l'ensemble des symboles terminaux (par exemple : Marc, livre, Alice, mange, lit, pomme, une, un) est l'ensemble des symboles non-terminaux (par exemple : sujet, verbe, complément, article, nom) est l'ensemble des productions de la grammaire (c'est-à-dire les associations des symboles non-terminaux avec les symboles terminaux) (exemple, voir la capture d'écran d'une slide ci-dessous). On va voir plus tard que les productions sont des règles de remplacement. est le symbole initial qui entame la génération de la grammaire. Par convention, ce sera justement
Conventions
- Par convention, les symboles en lettres latines minuscules représentent des symboles terminaux
- Les symboles latins majuscules représentent des symboles non-terminaux
- Les symboles en lettres grecs minuscules représentent des suites de symboles quelconques (terminaux ou pas)
- Les lettres latines minuscules allant de
à sont considérées comme des suites de symboles terminaux. - Les lettres latines majuscules allant de
à sont considérées comme des symboles quelconques
Dérivation
L'opération de base qui est effectuée dans une grammaire est la dérivation, autrement dit le fait de convertir des symboles non-terminaux en symboles terminaux sur base des règles de production de la grammaire. Cette opération est représentée par le symbole
Ainsi si la grammaire indique que
Le langage qui sera généré d'une grammaire est noté
Il y a 2 types de dérivation, la dérivation à gauche et la dérivation à droite, autrement dit que l'on va d'abord s'occuper du terme le plus à gauche ou du terme le plus à droite. Voici un exemple venant des tests :
À savoir que la barre verticale dans ce cas veut dire "ou". Donc la première production veut dire "E peut devenir E+T ou E-T ou T" par exemple.
Dans une dérivation à droite, on aurait à la place toujours commencée par dériver le symbole non terminal le plus à droite.
Grammaire ambigüe
Une grammaire est dite ambigüe si un mot peut être généré par 2 dérivations de gauche non équivalentes. Voici un exemple de grammaire ambigüe :
Donc pour enlever l'ambiguïté, il faut forcer la dérivation dans un certain sens, par exemple avec les nouvelles règles de productions suivante :
Tout langage généré par une grammaire ambigüe est dit intrinsèquement ambigu et ce type de langage est proscrit en informatique.
La dénomination de langage déterministe s'applique à tout langage issu de grammaire non ambigüe.
Les types de grammaires
Il existe différents types de grammaires en fonction de la complexité de leurs règles de productions :
- Type 0 (sans restriction) : les grammaires telles que
(soit une suite donne une autre) - Type 1 (contextuelle) : les grammaires telles que
(soit un symbole non-terminal est entouré d'au moins 2 mots qui donne le contexte. Le remplacement du symbole terminal va dépendre du contexte dans lequel il se trouve - Type 2 (algébrique ou non contextuelle) : les grammaires telles que
sont la même chose que le type 1 sauf que le contexte est vide - Type 3 (régulières) : les grammaires telles que
(alors appelée linéaire à droite) ou (alors appelée linéaire à gauche). Où le symbole non-terminal d'une règle est toujours placé d'un côté ou de l'autre des symboles non-terminaux. Ce type de grammaire engendre des langages rationnels, c'est-à-dire un langage qui peut être reconnu par un automate fini
No Comments