Théorie des langages/Histoire et notations

Historique et notations

Histoire de la théorie des langages

En 1956, Noam Chomsky propose une classification des langages formels, connue sous le nom de Hiérarchie de Chomsky. Cette classification permet l'étude de différents types de langages que nous allons aborder dans cette leçon.

Notations

• La concaténation de deux caractères a et b se note $a.b$, ou par abus de notation $ab$
• La répétition d'un caractère a, n fois se note $a^{n},n\in \mathbb {N}$
• La répétition d'un caractère un nombre quelconque de fois entre 0 et $\infty$ se note $a^{*}$
• La répétition d'un caractère un nombre quelconque de fois strictement positif se note $a^{+}$
• Le mot vide (sans aucune lettre) est noté $\epsilon$ (ou parfois aussi $\Lambda$)

Début de l'exemple

Exemple

• L'expression $ab^{*}a$ peut correspondre aux mots : aa, aba, abba, ...
• L'expression $aa^{*}$ est équivalente à $a^{+}$

Fin de l'exemple