« Théorie des langages/Définitions » : différence entre les versions
Contenu supprimé Contenu ajouté
Aucun résumé des modifications |
réorganisation des définitions existantes |
||
Ligne 8 :
= Définitions et notations =
Vous trouverez dans ce chapitre les notations et définitions permettant de travailler sur les langages par la suite
== Notations ==
Ligne 24 ⟶ 26 :
=== Les mots ===
La structure de base d'un langage est un alphabet.
* le mot vide <math>\epsilon</math> est un mot sur <math>\Sigma</math>▼
La structure supérieur à l'alphabet sont les mots, définis comme suit.
* Si <math>a \in \Sigma</math>, et <math>\omega</math> un mot sur <math>\Sigma</math>, alors <math>a.\omega</math> est un mot sur <math>\Sigma</math>▼
{{Définition|contenu='''Mot''' : l'ensemble des mots sur un alphabet <math>\Sigma</math> est défini récursivement de la manière suivante :
▲
}}
On note <math>\Sigma^*</math> l'ensemble des mots sur <math>\Sigma</math>, et <math>\Sigma^+</math> l'ensemble des mots autres que <math>\epsilon</math>
Lorque l'on travaille avec les mots, plusieurs choses sont é définir
* <math>|\epsilon| = 0|</math>▼
* si <math>\omega = a.\omega '</math> avec <math>a \in \Sigma, \omega' \in \Sigma^*</math>, alors <math>|\omega| = 1 + |\omega'|</math> }}
* '''concaténation de mots''' : on étend la concaténation de deux caractères à des mots, définie par :▼
* si <math>\omega' = a.u</math> avec <math>a \in \Sigma</math> et u un mot sur <math>\Sigma</math>, alors <math>\forall \omega \in \Sigma^*, \omega'.\omega = (a.u).\omega = a.(u.\omega)</math>▼
La concaténation des mots
▲{{Définition|contenu=* '''concaténation de mots''' : on étend la concaténation de deux caractères à des mots, définie par :
▲
}}
=== Les langages ===
| |||