2. Langages rationnels

Les langages rationnels sont une classe de langages (notée Rat(A*)) définie de manière inductive sur P(A*) en utilisant uniquement les trois opérations ∪, × et *.


Langage rationnel/réguliers

Soit A un alphabet. Les langages rationnels sur A (appelés aussi langages réguliers) sont les éléments de la classe Rat(A*) définie inductivement de la façon suivante : Rat(A*) est le plus petit sous-ensemble de P(A*) tel que :

  1. ∅ ∈ Rat(A*);
  2. {ε} ∈ Rat(A*);
  3. ∀a ∈ A, {a} ∈ Rat(A*);
  4. Si L1 ∈ Rat(A*) et L2 ∈ Rat(A*) alors L1∪L2 ∈ Rat(A*);
  5. Si L1 ∈ Rat(A*) et L2 ∈ Rat(A*) alors L1×L2 ∈ Rat(A*);
  6. Si L1 ∈ Rat(A*) alors L1* ∈ Rat(A*).

Par exemple, si l'on considère l'alphabet A={a,b,c}, alors l'ensemble des mots qui ne sont formés que de a est dans Rat(A*). Ce langage est {a}*. On peut l'obtenir à partir des points 3, puis 6 de la définition qui précède. De même, {a} ∪ {b} ∈ Rat(A*), {b} × {a} ∈ Rat(A*)... L'ensemble des mots sur A commençant par un b est également un langage de Rat(A*). Ce langage est {b} × ({a} ∪ {b} ∪ {c})*. Il est obtenu en applicant successivement les points 3 (3 fois), 4 (2 fois), 6 (1 fois) et 5 (1 fois).


Théorème des parties finies

Toute partie finie L de A* est dans Rat(A*).

Idée de démonstration :

Comme toute partie finie peut être vue comme la réunion de singletons, L peut être obtenu par un certain nombre d'applications des points 1 à 5 (démonstration par induction des langages rationnels, en particulier sur le cardinal de L) et en utilisant le théorème de décomposition unique d'un mot.

Par exemple, le langage L={0,1,00,11,000,111} sur l'alphabet {0,1,2} est-il un langage rationnel ? Il est construit par l'union de 6 langages rationnels {0}, {1}, {00}, {11}, {000} et {111}. En effet, les deux premiers sont des cas de base pour la définition (point 3) et les 4 suivants correspondent au produits de langages rationnels (par exemple, {00} = {0} × {0}). Or, la définition des langages rationnels indique que l'union de deux langages rationnels est un langage rationnel (point 4) et que le produit de deux langages rationnels est un langage rationnel. Donc L est bien rationnel.

On peut donc construire à l'aide des opérateurs de la définition précédente de nombreux langages désignés par des expressions mathématiques comme par exemple L={(({a}∪{b})*×{a})*×({b}×{c})*}, ce qui, en appliquant les définitions peut se simplifier en L={({a,b}*×{a})*×{bc}*}. Cette écriture toutefois reste lourde, en particulier à cause des nombreuses accolades qu'elle comporte. Il existe donc pour les langages rationnels une écriture simplifiée, plus compacte et pratique : c'est ce qu'on appelle les expressions rationnelles. Chaque expression rationnelle décrit un langage rationnel précis.

Exercices et tests :

Exercice 2.1. Soit l'alphabet A={0,1}, le langage décrivant les symboles de la table ASCII en binaire est-il un langage rationnel ? Aide

Solution

Exercice 2.2. Soit l'alphabet A={0,1}, le langage décrivant les chaînes de caractères (en Pascal ou C par exemple) en binaire est-il un langage rationnel ? Aide

Solution

mardi, 25/11/03 9:32