Grammaire universelle
La grammaire universelle a été pensé par Noam Chomsky, elle a pour but de s'appliquer à n'importe quel langage qu'il soit informatique, écrit ou verbal.
| Sommaire |
Définition
La grammaire d'un langage est définie grâce à quatre éléments :
- T (ensembles de mots) : terminaux
- N : non-terminaux
- R : règles
- S (S ∈ N) : symbole de départ
Les règles définissent les lois de construction du langage, sa grammaire. En français par exemple, la structure : sujet + verbe + compléments est un élément de grammaire. Il est bien entendu que les langages de notre planète ont des grammaires bien plus complexes que celle des langages de programmation.
4 catégories
Selon son auteur, il y a 4 familles de grammaires dont tous les langages font partie.
régulière ∈ hors contexte ∈ contextuelle ∈ générale
générale
aucune règle
Cette catégorie est impossible à traiter, la grammaire étant trop faible le temps pour savoir si une phrase appartient ou non à celle-ci n'est pas forcément fini.
contextuelle
(N ∪ T)* ↦ (N ∪ T)*
Où la seconde partie est plus petite que la première (ce qui permet lors de la recherche de ne pas poursuivre trop longtemps de mauvaises voies).
Contextuelle car le remplacement d'un élément non-terminal par un élément terminal peut dépendre des éléments autour de lui, de son contexte.
hors contexte
N ↦ (N ∪ T)*
Ici plus de contexte, ce qui signifie que les éléments non-terminaux sont traités individuellement.
régulière
N ↦ T N ↦ NT
La plus restrictive des 4.
exemple
une chaîne commence par un a et se termine par un z, elle peut contenir 0 à n = séparé par 1 à n - entre elles.
Mots (valides) :
- az
- a=z
- a=-=z
- a-=-=-z
- a-----z
Réponse :
T = {a,z,=,-}
N = {S,A,B}
S = {S}
R = {
S ↦ Az,
A ↦ A-,
A ↦ B=,
B ↦ A-,
A ↦ a,
B ↦ a
}