Leçons de niveau 15

Théorie des langages/Définitions

Une page de Wikiversité.
Sauter à la navigation Sauter à la recherche
Début de la boite de navigation du chapitre
Définitions
Icône de la faculté
Chapitre no 1
Leçon : Théorie des langages
Retour auSommaire
Chap. suiv. :Histoire et notations
fin de la boite de navigation du chapitre
Icon falscher Titel.svg
En raison de limitations techniques, la typographie souhaitable du titre, « Théorie des langages : Définitions
Théorie des langages/Définitions
 », n'a pu être restituée correctement ci-dessus.

Vous trouverez dans ce chapitre les notations et définitions permettant de travailler sur les langages par la suite

Notations[modifier | modifier le wikicode]

  • 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


Définitions[modifier | modifier le wikicode]

Les mots[modifier | modifier le wikicode]

La structure de base d'un langage est un alphabet.


La structure supérieure à l'alphabet sont les mots, définis comme suit.


On note l’ensemble des mots sur , et l’ensemble des mots autres que

Lorsque l’on travaille avec les mots, plusieurs choses sont à définir


La concaténation des mots


Les définitions suivantes permettent de travailler sur une partie des mots


Les langages[modifier | modifier le wikicode]