5. Langages et opérations


Langage
- version 1 -

Un langage L sur un alphabet A est un ensemble de chaînes (ou ensemble de mots) sur A. L est donc un sous-ensemble de A*, autrement dit L ⊆ A*.

Par conséquent, l'ensemble des langages L sur A est l'ensemble P(A*) des parties de A*, autrement dit : L ∈ P(A*).

Par exemple, si l'on considère l'alphabet A = {0, 1} alors L1 = {0, 00, 1, 01, 11, 10 } est un langage sur A. De même, pour tout entier naturel n, An est un langage sur A, où, rappelons le, An est l'ensemble des mots de longueur n sur A. Si de plus, pour toute lettre a, an désigne le mot formé de n symboles a consécutifs, alors L2 = { 0n1n | n ≥ 0}, L3 = {0n10m | n ≥ 0, m ≥ 1}, L4 = {1n | n ≥ 2} et L5 = {0i | i ≥ 0} = {0}* sont d'autres exemples de langages sur A.

Parmi tous les langages sur un alphabet A donné, on en distingue quelques uns particuliers, dont par exemple les suivants.


Langage prefixe
ou suffixe

Étant donné un alphabet A, parmi tous les langages L de P(A*) :

  • Le langage neutre est celui dont le seul mot est la chaîne vide : L = {ε}.
  • Le langage vide est celui qui ne contient aucun mot, soit L= ∅.
  • Un langage fini est un langage qui contient un nombre fini de mots.
  • Un langage infini est un langage non vide et non fini.
  • Un langage L est dit posséder la propriété préfixe (resp. suffixe) si aucune chaîne de L n'est préfixe propre (resp. suffixe propre) d'une autre chaîne de L.

Par exemple, L = {aib | i ≥ 0 } = {b, ab, aab, aaab...} est dit préfixe mais n'est pas suffixe. L = {an | n ∈ N} n'est ni l'un ni l'autre.

Notons par ailleurs que ∅ ≠ {ε}.

Comme les langages sont des ensembles, on peut leur appliquer les opérations ensemblistes classiques : union, intersection, complémentation, etc. De plus, par extension de la concaténation des mots aux langages, on peut définir quelques autres opérateurs.


Union,
Intersection,
Différence,
Complémentaire

Soit A un alphabet. On définit sur les langages de P(A*) les opérateurs suivants : soient L et M deux langages sur A,

Opérateurs ensemblistes classiques :

  • union : L ∪ M = {x | x ∈ L ou x ∈ M} ;
  • intersection : L ∩ M = {x | x ∈ L et x ∈ M};
  • différence (ou exclusion) : L\M = L-M = {x | x ∈ L et x ∉ M};
  • complémentaire sur A* : Comp(L)= A*\L = {x | x ∈ A* et x ∉ L};

Opérateurs induits par la concaténation des mots :

  • produit des langages : LM = L×M = {xy | x ∈ L et y ∈ M};
  • fermeture de Kleene : L* = ∪i=0..∞ Li où L0 = {ε} et Ln = LLn-1 = Ln-1L ;
  • fermeture positive : L+= ∪i=1..∞ Li.

Par extension, le produit est parfois appelé "concaténation de deux langages". Cette concaténation est notée × (et le symbole × est souvent omis), mais il s'agit bien de deux concaténations différentes : l'une entre mots et l'autre entre ensembles de mots. Intuitivement, la concaténation de deux langages est l'ensemble des mots obtenus en concaténant un mot du premier langage avec un mot du second. Par exemple, si L1={a,bc} et L2={de,f} alors L1 × L2={ade, af, bcde, bcf}.

Sur ces opérateurs entre langages, on a, entre autres, les quelques propriétés suivantes :

Jusqu'ici, un langage sur un alphabet A pouvait être n'importe quelle partie dans P(A*) , ce qui est très vaste. En particulier, au moment de vérifier si un mot appartient à un langage, il est utile d'avoir une caractérisation précise de ce langage, ce qui n'est pas toujours évident si l'on considère une partie infinie quelconque dans P(A*) . On va donc, d'un point de vue pragmatique, s'intéresser à des classes de langages particuliers pour lesquels on a des descriptions finies, utilisables pour décider si oui ou non, un mot est dans un langage. Parmi ces types de langages, on s'intéresse en premier lieu aux langages rationnels.

Exercices et tests :

Exercice 5.1. Montrer que le produit de deux langages préfixes est un langage préfixe. Aide

Solution

jeudi, 11/12/03 10:45