Retour
Alphabets et mots
Un alphabet $\Sigma$ est un ensemble fini de symboles. Dans la suite $a, b, c, d$ représenteront des symboles.
Mot
Un mot sur $\Sigma$ est une suite finie de symboles appartenant à $\Sigma$. Dans la suite $u, v, w$ représenteront des mots.
La longueur d'un mot $w$, notée $|w|$, est le nombre de symboles composant $w$. Par exemple, si $w = abaa$, alors $|w| = 4$.
L'ensemble des mots de longueur $n$ sur $\Sigma$ est noté $\Sigma^n$, et l'ensemble de tous les mots (y compris le mot vide $\varepsilon$) est noté $\Sigma^*$.
Le mot vide, noté $\varepsilon$, est le mot de longueur zéro.
Un mot $u$ est un préfixe de $w \in \Sigma^*$ s'il existe un mot $v \in \Sigma^*$ tel que $w = uv$.
Un mot $u$ est un suffixe de $w \in \Sigma^*$ s'il existe un mot $v \in \Sigma^*$ tel que $w = vu$.
Un mot $u$ est un facteur de $w \in \Sigma^*$ s'il existe des mots $v, v' \in \Sigma^*$ tels que $w = vuv'$.
Un sous-mot de $w$ est une suite de symboles apparaissant dans $w$, pas nécessairement contigus.
Opération sur les mots
La concaténation de deux mots $u$ et $v$, notée $uv$, est le mot obtenu en plaçant $v$ immédiatement après $u$. Par exemple, si $u = ab$ et $v = bac$, alors $uv = abbac$.
La puissance $n$-ième d'un mot $w$, notée $w^n$, est définie inductivement :
$$w^0 = \varepsilon, \quad w^{n+1} = w^n \cdot w.$$
Par exemple, si $w = ab$, alors $w^3 = abab \cdot ab = ababab$.
Le miroir (ou renversement) d'un mot $w$, noté $w^R$, est le mot obtenu en inversant l'ordre des symboles de $w$. Par exemple, si $w = abc$, alors $w^R = cba$.
Langage
Un langage $L$ sur un alphabet $\Sigma$ est un sous-ensemble de $\Sigma^*$. Ainsi, $L \subseteq \Sigma^*$. Par exemple, si $\Sigma = \{a, b\}$, $L = \{a, ab, bba\}$ est un langage.
Opérations sur les langages
Soient $L_1$ et $L_2$ deux langages sur un alphabet $\Sigma$.
Union : $L_1 \cup L_2 = \{w \mid w \in L_1 \text{ ou } w \in L_2\}$
Concaténation : $L_1 \cdot L_2 = \{uv \mid u \in L_1 \text{ et } v \in L_2\}$.
Étoile de Kleene : $L^* = \bigcup_{n=0}^\infty L^n$, où $L^0 = \{\varepsilon\}$ et $L^n = L \cdot L^{n-1}$.
