Mots et langage
Définition
On appelle alphabet ou vocabulaire tout ensemble non vide fini. Les éléments d'un vocabulaire sont appelés lettres ou caractères.
Par exemple \( \Sigma=\{0,1\}\) défini l'alphabet du langage binaire et \( 0\) et \( 1\) sont les lettres de cet alphabet.
Définition
Soit \( \Sigma\) un alphabet.
- \( (i)\)
- Soit \( n\in \N_{{>}0}\) . On appelle mot de longueur \( n\) tout \( n\) -uplet \( a=(a_1,\dots,a_n)\in \Sigma^n\) . On note plus simplement \( a=a_1\dots a_n\) . On note \( n=\norm{a}\) .
- \( (ii)\)
- On note \( \varepsilon\) le mot vide (ie qui ne contient aucune lettre) ; \( \norm{\varepsilon}=0\) .
- \( (iii)\)
- Pour tout \( n\in \N\) , on note \( \Sigma^n\) l'ensemble de tous les mots de longueur \( n\) ; en particulier \( \Sigma^0=\{\varepsilon\}\) et \( \Sigma^1=\Sigma\) .
- \( (iv)\)
- On définit l'étoile de Kleene sur \( \Sigma\) , notée \( \Sigma^*\) , comme l'ensemble de tous les mots quelque soit leur longueur.
\[\Sigma^*=\bigcup_{n\in \N}\Sigma^n\]
Par exemple sur l'alphabet \( \Sigma=\{0,1\}\) du langage binaire \( \Sigma^3=\{000,001,010,011,100,101,110,111\}\) et
\[\Sigma^*=\{\varepsilon,0,1,00,01,10,11,000,001,010,011,100,101,...\}\]
Si \( \Sigma=\{a\}\) alors \( \Sigma^*=\{\varepsilon,a,a^2,a^3,a^4,...\}\) .
Définition
Soit \( \Sigma\) un alphabet. Un langage sur \( \Sigma\) est une partie de \( L\left(\Sigma\right)\) de \( \Sigma^*\) . Les éléments de \( L\left(\Sigma\right)\) sont appelés les mots du langage.
Par exemple, toujours avec \( \Sigma=\{0,1\}\) , on considère le langage \( L\left(\Sigma\right)\) formé de tous les mots de \( \Sigma^*\) ne commençant pas par \( 0\) :
\[L\left(\Sigma\right)=\{\varepsilon,1,10,11,100,101,110,111,1000,1001,...\}\]
Concaténation
Étant donné un alphabet \( \Sigma\) on peut effectuer sur les langages les opérations ensemblistes courantes : l'intersection, l'union et la complémentation. On peut également Concaténer les mots.
Définition
Soient \( \alpha\) et \( \beta\) deux mots sur un alphabet \( \Sigma\) tel que \( \norm{\alpha}=n\) et \( \norm{\beta}=m\) . On définit la Concaténation de \( \alpha\) de \( \beta\) , noté \( \alpha\circ\beta\) ou plus simplement \( \alpha\beta\)
par la règle :
\[\forall 1\leqslant k\leqslant n+m,\qquad (\alpha\beta)_k=\left\{
\begin{array}{rl}
\alpha_k&\text{si } k\leqslant n\text{,}\\
\beta_{k-n}& \text{sinon.}
\end{array}
\right.\]
on dit que \( \alpha\) est le facteur gauche ou le préfixe de \( \alpha\beta\) et \( \beta\) et le facteur droit ou le suffixe.
Par exemple, sur l'alphabet binaire \( 001\circ101 = 001101\) .
Proposition
Pour tout alphabet \( \Sigma\) , la Concaténation définit une opération interne sur \( \Sigma^*\)
\begin{eqnarray*}
\circ : \Sigma^*\circ \Sigma^*&\longrightarrow&\Sigma^*\\
(\alpha,\beta)&\longmapsto&\alpha\circ\beta
\end{eqnarray*}
satisfaisant :
- (Associativité)
- \( \forall \alpha, \beta,\gamma \in \Sigma^*\) , \( (\alpha\circ\beta)\circ\gamma=\alpha\circ(\beta\circ\gamma)\) .
- (Élément neutre)
- \( \forall \alpha \in \Sigma^*\) , \( \alpha\circ\varepsilon=\varepsilon\circ\alpha=\alpha\) .
- (Longueur)
- \( \forall \alpha, \beta\in \Sigma^*\) , \( \norm{\alpha\circ\beta}=\norm{\alpha}+\norm{\beta}\) .
Démonstration
Vérifions l'associativité, le reste est trivial. Notons \( \norm{\alpha}=n\) , \( \norm{\beta}=m\) et \( \norm{\gamma}=p\) et fixons un entier \( 1\leqslant k\leqslant n+m+p\) . Alors
\[
((\alpha\circ\beta)\circ\gamma)_k=\left\{
\begin{array}{rl}
(\alpha\circ\beta)_k&1\leqslant k\leqslant n+m\\
\gamma_{k-(n+m)}& n+m+1\leqslant k\leqslant n+m+p
\end{array}\right.
=\left\{\begin{array}{rl}
\alpha_k&1\leqslant k\leqslant n\\
\beta_{k-n}&n+1\leqslant k\leqslant n+m\\
\gamma_{k-(n+m)}& n+m+1\leqslant k\leqslant n+m+p
\end{array}
\right.
\]
\[
(\alpha\circ(\beta\circ\gamma))_k=\left\{
\begin{array}{rl}
\alpha_k&1\leqslant k\leqslant n\\
(\beta\circ\gamma)_{k-n}& n+1\leqslant k\leqslant n+m+p
\end{array}\right.
=\left\{\begin{array}{rl}
\alpha_k&1\leqslant k\leqslant n\\
\beta_{k-n}&n+1\leqslant k\leqslant n+m\\
\gamma_{(k-n)-m}& n+m+1\leqslant k\leqslant n+m+p
\end{array}
\right.
\]
On observe que les deux expressions sont identiques (puisque \( k-(n+m)=(k-n)-m\) ).
Remarque
La Concaténation n'est pas commutative à moins que \( \Sigma\) ne soit un singleton.
Définition
Soient \( \alpha\) et \( \alpha'\) deux mots sur un alphabet \( \Sigma\) . On dira que \( \alpha'\) est un sous-mot de \( \alpha\) s'il existe des mots \( \pi\) et \( \sigma\) tel que
\( \alpha=\pi\alpha'\sigma\)
