Aller au contenu

Théorie des langages/Histoire et notations

Leçons de niveau 15
Une page de Wikiversité, la communauté pédagogique libre.
Début de la boite de navigation du chapitre
Histoire et notations
Icône de la faculté
Chapitre no 2
Leçon : Théorie des langages
Chap. préc. :Définitions
Chap. suiv. :Les mots
fin de la boite de navigation du chapitre
En raison de limitations techniques, la typographie souhaitable du titre, « Théorie des langages : Histoire et notations
Théorie des langages/Histoire et notations
 », n'a pu être restituée correctement ci-dessus.

Historique et notations

[modifier | modifier le wikicode]

Histoire de la théorie des langages

[modifier | modifier le wikicode]

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.

  • La concaténation de deux caractères a et b se note , ou par abus de notation
  • La répétition d'un caractère a, n fois se note
  • La répétition d'un caractère un nombre quelconque de fois entre 0 et se note
  • La répétition d'un caractère un nombre quelconque de fois strictement positif se note
  • Le mot vide (sans aucune lettre) est noté (ou parfois aussi )
Début de l'exemple
Fin de l'exemple