====== Définitions ======
===== Alphabet et Mots =====
?? un alphabet
:: un ensemble fini non vide dont les éléments sont appelés des **lettres** . !!
?? un mot
:: un mot sur un alphabet A est une suite finie d'éléments de A. La suite de zéro lettre est appelée le **mot vide** et noté ε.!!
* L'ensemble des mots sur l'alphabet A est noté A*
* L'ensemble des mots sur l'alphabet A excepté le mot vide ε est noté A+
* A^{+} = A^{*} \setminus \epsilon
La __longueur__ d'un mot x est la longueur de la suite associée au mot x et est notée |x|.
On note x[i], avec 0 ≤ i ≤ |x|-1, la lettre à l'indice i de x avec par convention une numérotation des indices à partir de 0. L'indice i représente une position sur x si x ≠ ε. La j-ième lettre de x est la lettre à la position j-1 sur x et x=x[0]x[1]...x[|x|-1].
L'__égalité__ de deux mots quelconques est définie par
| x = y ^ <=> | |x|=|y| x[i]=y[i] pour 0 ≤ i ≤ |x|-1.
L'ensemble des lettres sur lequel est formé le mot x est noté alph(x).
?? produit
?? concaténation
:: de deux mots x et y est le mot composé des lettres de x puis de celles de y dans cet ordre. Ce produit est noté xy ou x⋅y (pour faire apparaître une décomposition du mot résultant).!!
:: l'élément neutre pour le produit est ε.!!
?? puissance
:: Pour tout mot x et tout entier n ≥0, la n-ième puissance du mot x notée xn est définie par
* x0 = ε
* xk = xk-1 ⋅x (k > 0)
!!
Sont notés respectivement zy-1 et x-1z les mots x et y lorsque z = x⋅y.
?? renversé
?? image miroir
:: Le renversé (ou image miroir) du mot x est le mot x~ défini par x~ = x[|x|-1]x[|x|-2]...x[0]
!!
?? facteur
:: un mot x est un facteur d'un mot y s'il existe deux mots u et v tels que y = u⋅x⋅v .
?? préfixe :: lorsque u = ε, x est un __préfixe__ de y !!
?? suffixe :: lorsque v = ε, x est un __suffixe__ de y !!
?? propre :: un facteur, préfixe ou suffixe x d'un mot y est qualifié de __propre__ si x ≠ y. !! !!
Une occurrence d'un mot non vide x dans un mot y, apparaît lorsque x est un facteur de y. Une occurrence de x peut être caractérisée par une position sur y. Une occurrence de x __débute__ à la __position__ (gauche) i sur y lorsque y[i..i+|x|-1] = x. Il est également possible de considérer la __position droite__ i+|x|-1 où l'occurrence se termine.
Les notations avec des crochets pour les lettres des mots sont étendues aux facteurs. On définit le facteur x[i..j] du mot x par x[i..j]=x[i≠x[i+1]...x[j] pour tous les entiers i et j satisfaisant
- 0 ≤ i ≤ |x|
- -1 ≤ j ≤ |x|-1
- i ≤ j + 1
Lorsque i = j+1, le mot x[i..j] = x[j+1 ..j] = x[i..i-1], est vide.
===== Langages =====
?? langage :: Tout sous-ensemble de A* est un langage X sur l'alphabet A. !!
Le produit défini sur les mots est étendu aux langages en posant XY = X⋅Y = {xy : (x,y)∈ X × Y} pour tous les langages X et Y.
Similairement ((c'est pas du français, ça)), la puissance définie sur les mots est étendue aux langages en posant X0 = {ε} et Xk=Xk-1 X avec k > 0.
* L'étoile de X est le langage X^* = \cup_{n\geq 0} X^n
* Le langage X+ est défini par X^+ = \cup{n\geq 1} X^n
La longueur définie sur les mots est étendue aux langages en posant |X| = \sum_{x\in X} |X| .
Les ensembles des facteurs, des préfixes et des suffixes des mots d'un langage X sont des langages particuliers notés respectivement Fact(X),Préf(X) et Suff(X).
===== Périodicité et Bords =====
FIXME : à rajouter
==== Proposition ====
Soient x un mot non vide et n le plus grand des entiers k pour lequel Bordk(x) est défini (soit Bordn(x)=ε). Alors (Bord(x), Bord2(x)...Bordn(x)) est la suite des bords de x classés par ordre décroissant de longueur, et
(|x|-|Bord(x)|, |x|-|Bord2(x)|,...|x|-|Bordn(x)|) est la suite des périodes de x classées par ordre croissant.
===== Puissance et Primitivité =====
==== Proposition ====
Soient x et y deux mots. S'il existe deux entiers naturels non nuls m et n tels que xm = yn alors x et y sont des puissances d'un certain mot z.
=== Exercice ===
Trouver un exemple de xm = yn et x,y puissances de z.
* x = ''abab''
* y = ''ababab''
* x3 = y2 = (ab)6 => z=''ab''
==== Proposition ====
Un mot non vide est primitif si et seulement s'il n'est facteur de son carré qu'en tant que préfixe et suffixe.
=== Exemple ===
* mot primitif : ''aba'' ou ''abaab''
* mot non primitif : ''baba'' -> ''ba⋅baba⋅ba'' => facteur au milieu, pas seulement en préfixe et suffixe
?? conjugués
:: Deux mots x et y sont **conjugués** s'il existe deux mots u et v tels que x = u⋅v et y = v⋅u. Deux mots conjugués ont la même longueur. La conjugaison et une relation d'équivalence. Elle n'est pas compatible avec le produit.!!
^ x = u⋅v et y = v⋅u | u = A, v=AC | x=AAC, y=ACA |
^ | u = CA, y = C | x=CAC, y = CCA |
AAC -> ACA -> CAA -> AAC => 20 classes de trinucléotides conjugués.
==== Proposition ====
Deux mots non vides x et y sont conjugués si et seulement s'il existe un mot z tel que x⋅z=z⋅y.
| x⋅z = z⋅y = u⋅v⋅z = z⋅v⋅u |
Exemple de mot z pour AAC et ACA : z=A <= AACz = zACA <=> AACA = AACA
----
[[search_2|]]