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.
Exemple
L'ensemble \( \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\]
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,...\}\) .
Exercice
Si \( \Sigma=\varnothing\) , décrire \( \Sigma^*\) .
Exercice
Soit \( \Sigma\) un ensemble fini et non vide. Vérifier que l'application \( \norm{\bullet}:\Sigma^*\rightarrow\N\) est surjective. A quelle condition est-elle injective ?
Définition
Soit \( \Sigma\) un alphabet. Un langage sur \( \Sigma\) est une partie de \( L\) de \( \Sigma^*\) . Les éléments de \( L\) sont appelés les mots du langage.
Exemple
Toujours avec \( \Sigma=\{0,1\}\) , on considère le langage \( L\) formé de tous les mots de \( \Sigma^*\) ne commençant pas par \( 0\) :
\[L=\{\varepsilon,1,10,11,100,101,110,111,1000,1001,...\}\]
Proposition
Soient \( L_1\) et \( L_2\) deux langages sur un alphabet \( \Sigma\) . Alors \( L_1\cup L_2\) , \( L_1 \cap L_2\) et \( \overline{L_1}\) sont des langages sur \( \Sigma\) .
Démonstration
Triviale
Exercice
Est-ce que \( L=\varnothing\) est un langage sur \( \Sigma\) ?
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.
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\) ).
Exercice
A quelle condition sur un alphabet fini \( \Sigma\) , la concaténation dans \( \Sigma^*\) est commutative ?
Définition
Soient \( L_1\) et \( L_2\) deux langages sur un alphabet \( \Sigma\) . On défini l'ensemble \( L_1L_2\) le langage des mots concaténés.
\[L_1L_2=\left\{m\in \Sigma^*\Big|\exists l_1\in L_1,\ \exists l_2\in L_2, \ m=l_1l_2\right\}\]
Exercice
Déterminer \( \varnothing L\) et \( L\varnothing\) pour tout langage \( L\) sur un alphabet \( \Sigma\) .
Proposition
Soient \( L_1\) , \( L_2\) et \( L_3\) des langages sur un alphabet \( \Sigma\) .
- \( (i)\) .
- \( L_1L_2\) est un langage sur \( \Sigma\) .
- \( (ii)\) .
- \( L_1\{\varepsilon\}=\{\varepsilon\}L_1=L_1\) .
- \( (iii)\) .
- \( L_1\left(L_2L_3\right)=\left(L_1L_2\right)L_3\)
Définition
Soit \( L\) un langage sur un alphabet \( \Sigma\) . On définit l'étoile de Kleene de \( L\) , l'ensemble noté \( L^*\) définit de manière récursive par les règles
\begin{eqnarray*}
L^0&=&\{\varepsilon\}\\
\forall n \in \N, \ L^{n+1} &=& L^nL\\
L^* &=& \bigcup_{n\in \N} L^n
\end{eqnarray*}
Exercice
Soit \( \Sigma\) un alphabet non vide tel que \( a\in\Sigma\) .
Décrire \( L^*\) dans chacun des cas suivants :
- \( L_1=\varnothing\)
- \( L_2=\{\varepsilon\}\)
- \( L_3=\{a\}\)
