Chapitre 1 Langages

1.1 Alphabets et mots

Définition 1.1 Un alphabet est un ensemble fini \(\mathcal{A}\). Un élément \(a\in\mathcal{A}\) est appelé lettre, symbole ou caractère selon le contexte.

Définition 1.2 Soit \(\mathcal{A}\) un alphabet. Un mot est une suite finie d’éléments de \(\mathcal{A}\). La longueur d’un mot est le nombre d’éléments de cette suite.

On note \(\mathcal{A}^k\) l’ensemble des mots de longueur \(k\in\mathbb{N}\) et \(\mathcal{A}^*\) pour l’ensemble de tous les mots sur l’alphabet \(\mathcal{A}\).

Un mot \(m\) s’écrit donc \(m_1m_2...m_n\) où les \(m_i\) sont des lettres de l’alphabet. Ici la longueur du mot \(m\) est donc \(n\).

Définition 1.3 On appelle mot vide l’unique mot de longueur 0. On le note \(\varepsilon\) et c’est bien un élément de \(\mathcal{A}^*\).

Exemple 1.1 Voici quelques exemples d’alphabets et de mots.

  1. L’alphabet latin contient 26 lettres a,b,c,d,…,z.
  2. Si \(\mathcal{A}=\{0,1\}\). Les mots sur l’alphabet \(\mathcal{A}\) sont les mots binaires.
  3. L’ensemble des caractères unicode forme un alphabet.
  4. Si \(\mathcal{A}=\{0,1,2,3,...,9\}\) est l’ensemble des chiffres arabes, les mots sur \(\mathcal{A}\) sont les nombres en écriture décimale.

Définition 1.4 Soit \(m=m_1m_2...m_k\) et \(m'=m'_1...m'_l\) deux mots sur un alphabet \(\mathcal{A}\). On appelle concaténation de \(m\) et \(m'\) le mot \(w\) de \(\mathcal{A}\) donné par \(w_1=m_1,w_2=m_2,\dots,w_k=m_k,w_k+1=m'_1,\dots,w_{k+l}=m'_l\), c’est-à-dire le mot \(m_1...m_km'_1...m'_l\). On notera \(m\cdot m'\) pour la concaténation de \(m\) et \(m'\).

Remarque. Pour le mot vide \(\varepsilon\) et tout autre mot \(m\), on a \(m\cdot \varepsilon=\varepsilon\cdot m=m\).

Définition 1.5 Soit \(m,p,s,f\) des mots sur un alphabet \(\mathcal{A}\).

  • On dit que \(p\) est un préfixe de \(m\) s’il existe \(m'\in\mathcal{A}^*\) tel que \(m=p\cdot m'\).
  • On dit que \(s\) est un suffixe de \(m\) s’il existe \(m'\in\mathcal{A}^*\) tel que \(m=m'\cdot s\).
  • On dit que \(f\) est un facteur de \(m\) s’il existe \(m',m''\in\mathcal{A}^*\) tel que \(m=m'\cdot f\cdot m''\).

Remarque.

  1. Les préfixes et les suffixes sont des cas particuliers de facteur.
  2. Le mot vide est facteur, préfixe et suffixe de n’importe quel autre mot.

1.2 Langages

Définition 1.6 Soit \(\mathcal{A}\) un alphabet. On appelle langage n’importe quel sous-ensemble de \(\mathcal{A}^*\), c’est-à-dire n’importe quel ensemble de mots sur \(\mathcal{A}\).

Exemple 1.2

  1. L’anglais est un langage sur l’alphabet latin.
  2. Les nombres pairs forment un langage sur l’ensemble des chiffres.
  3. Les numéros IBAN des comptes bancaires forment un langage sur l’ensemble \(\{1,\dots,9,a,\dots,z\}\). Ils vérifient les propriétés suivantes:
    • Les deux premiers caractères sont des lettres (pays)
    • Les deux suivants sont des chiffres (clé de contrôle pays)
    • Les 5 suivants sont des chiffres (code établissement)
    • Les 5 suivants sont des chiffres (code guichet)
    • Les 11 suivants sont des chiffres (numéro de compte bancaire)
    • Les 2 derniers caractères sont des chiffres (clé RIB inférieur à 97, c’est le reste modulo 97 du nombre formé du code établissement, code guichet et numéro de compte)
  4. Les mots sur l’alphabet latin qui se terminent par -ent forment un langage.

Remarque. Comme un langage est un sous-ensemble, on peut faire les opérations ensemblistes classiques et parler de réunion ou d’intersection de langages ou encore du langage complémentaire.

Remarque. L’ensemble de tous les mots \(\mathcal{A}^*\) est un langage, c’est le langage universel sur l’alphabet \(\mathcal{A}^*\).

Définition 1.7 Soit \(L_1,L_2\) deux langages sur un même alphabet \(\mathcal{A}\). La concaténation de \(L_1\) et \(L_2\) est le langage \(\{m_1\cdot m_2,\ m_1\in L_1,\ m_2\in L_2\}\).

Remarque. Si \(L\) est le langage vide (i.e. \(L=\emptyset\), ce qui est différent de \(L\) ne contient que le mot vide) alors pour tout autre langage \(L'\), on a \(L\cdot L'=L'\cdot L=\emptyset\).

Définition 1.8 On dit qu’un langage \(L\) est stable par concaténation si pour tous \(m,m'\in L,\ m\cdot m'\in L\).

Définition 1.9 (étoile de Kleene d'un langage) Soit \(L\) un langage sur un alphabet \(\mathcal{A}\). L’étoile de Kleene de \(L\) est le plus petit langage, noté \(L^*\), sur \(\mathcal{A}\) au sens de l’inclusion qui contient \(\varepsilon, L\) et stable par concaténation.

1.3 Exercices

Exercice 1.1 Soit \(\mathcal{A}\) un alphabet.

  1. Quel est le nombre de mot de longueur \(n\) ? La formule que vous obtenez fonctionne-t-elle encore pour \(n=0\) ?
  2. Soit \(m\) \(m'\) deux mots. Quelle est la longueur de \(m\cdot m'\) ?

Exercice 1.2 La concaténation vérifie-t-elle les propriétés suivantes ?

  1. associativité
  2. commutativité

Exercice 1.3

  1. Donner l’ensemble des mots sur l’alphabet suivant
    1. \(\mathcal{A}=\emptyset\).
    2. \(\mathcal{A}=\{a\}\).
  2. Donner les mots de longueur au plus 3 sur l’alphabet \(\mathcal{A}=\{a,b\}\).
  3. Soit \(\mathcal{A}=\{a, b, c\}\) un alphabet. Donner le langage \(L_1.L_2\) où \(L_1 = \{ab\}\) et \(L_2=\{bb, ca\}\).
  4. Le langage \(\{ab, bb\}\) sur l’alphabet \(\mathcal{A}=\{a, b\}\) est-il stable par concaténation ?

Exercice 1.4 Soit \(L\) un langage sur un alphabet \(\mathcal{A}\). Démontrer que \(L^*\) est l’ensemble des mots \(m\) sur \(\mathcal{A}\) qui s’écrivent \(m_1\cdot\dots\cdot m_n\) pour \(n\in\mathbb{N}\) et \(m_i\in L\) pour tout \(i\in\{1,\dots,n\}\).

Exercice 1.5 Soit \(L_1\) et \(L_2\) deux langages finis sur un même alphabet. On note \(\# L\) le cardinal d’un langage. Montrer que

\[\# (L_1\cdot L_2)\leq \# L_1\times\# L_2.\]

A-t-on égalité en général ?

Exercice 1.6 Montrer que la concaténation des langages est distributive sur la réunion, mais pas sur l’intersection. Plus précisément, pour trois langages \(L,L_1,L_2\) sur un même alphabet, montrer

  1. \(L\cdot(L_1\cup L_2)=(L\cdot L_1) \cup (L\cdot L_2)\),
  2. \(L\cdot(L_1\cap L_2)\subsetneq (L\cdot L_1) \cap (L\cdot L_2)\).