« 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éfinir
{{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=* '''concaténation de mots''' : on étend la concaténation de deux caractères à des mots, définie par :
* <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>
}}