« Théorie des langages/Définitions » : différence entre les versions
Contenu supprimé Contenu ajouté
réorganisation des définitions existantes |
|||
Ligne 37 :
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éfinition|contenu='''longueur d'un mot''' : la longueur d'un mot <math>\omega</math> est notée <math>|\omega|</math> et est définie récursivement comme suit :
* <math>|\epsilon| = 0|</math>
Ligne 44 :
La concaténation des mots
{{Définition|contenu=
* <math>\epsilon.\omega = \omega</math>
* 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>
}}
Les définitions suivantes permettent de travailler sur une partie des mot
{{Définition|contenu=
* '''Préfixe''' : <math>u \in \Sigma^*</math> est un préfixe de <math>v \in \Sigma^*</math> si <math>\exists w \in \Sigma^*, v = u.w</math>
* '''Suffixe''' : <math>u \in \Sigma^*</math> est un suffixe de <math>v \in \Sigma^*</math> si <math>\exists w \in \Sigma^*, v = w.u</math>
* '''Facteur''' : <math>u \in \Sigma^*</math> est un facteur de <math>v \in \Sigma^*</math> si <math>\exists w_1, w_2 \in \Sigma^*, v = w_1.u.w_2</math>
}}
|