E le mot vide (qui ne conti e nt a uc un e
lettre), é lé me nt ne utre pour la concaténation. Plusieurs opérations peuvent être
effectuées sur les langages. Si Let L'
sont deux langages, on peut définir L U L'
l' union (a u se n s de la th éo ri e des
ensemb les) des deux langages. LL' est
par définition le langage formé par les
mots qui so nt les concaténations des
mots de L avec les mots de L' . Ainsi,
LL' = {uv, avec u dans Let v dans L'}.
Ensuite, l'étoile de Kleene L * de Lest
le lan gage défin i par {E}U LULL U ...
Enfin , L c est le complémentaire d u langage L (c'est l'ense mbl e des mots fin is
qui apparti e nnent à A * mai s pas à L).
Amusons-nous sur un exemple .
Le langage {aa + b} * contient par exemple
aab o u bbaa mais pas ab. S aurez-vous
le démontrer à l'a ide d ' un rai sonne ment
rigoureux ?
Parmi tou s les langages co ncevables ,
les langages rationn els so nt dé fini s
ains i : pour chaque lettre a da ns A , {a}
est un la ngage ratio nne l ; le complémentaire d'un langage rationnel est un
langage rat ionnel ; l' union ou la concaténation de de ux langages rationnels est
un lan gage ration ne l, et l'étoil e d ' un
langage rationnel est un langage rationnel. On représente généra lement les langages rationnels par des express ion s
rat io nne lles :
• a est l'exp ression rationne lle dé notant
le langage {a} pour une le ttre a apparte na nt à A ,
• e + e' dé note l ' uni o n des la ngages
dénotés par e et e',
• ee' dénote la concaté nati o n des la ngages dé notés par e et e',
• e* dénote l' étoile de Kl eene du la ngage dé noté par e ,
• A *\e dénote le comp lé menta ire du
langage dé noté par e.
Par e xemp le, si o n cons idè re! 'a lphabet
A= {a, b}, le langage des mots fi ni sPOUR L'INFORMATIQUE
Type O
Langages rée. énumérables
Machines de Turing
Type I
Langages contextuels
Automates linéairement bornés
Type 2
Langages algébriques
Automates à pile
La hiérarchie de Chomsky est une classification des langages
formels et des grammaires formelles. Les automates finis
reconnaissent les langages rationnels tandis que les machines
de Turing peuvent calculer tout ce qui est calculable.
sant pa r ab est dé noté par A *ab et le
langage des mots com me nça nt par b,
fm issant par b et ne contenant jamais deux
a conséc utifs est dé noté par
b(ab + b) *, s ig nifi ant : « d ' abord, un b ,
sui vi d ' un nombre arb itra ire de mots
parmi ab et b » (convainq uez-vous bien
que nécessai reme nt tout mot ai n si
co nstruit finira par b).
Le langage {a"b" , avec n un e ntier quel -
conque} , qui est s impl eme nt { E, ab,
aabb , aaabbb .. . } , est un exemple célèbre
de langage non rationnel.
Les notations sur les langages rationne ls ne sont pas sans rappeler les expressions régulières : lorsque je veux vérifier
da ns cet art ic le que je n 'a i pas commen cé un paragraphe par un e lettre
minuscule , mon éd iteur de texte me
permet d ' utili ser l'express ion rég uliè re
\n[a-z], qui correspond à un caractère
de retour de lig ne (newline) su ivi d ' une
lettre minuscule , pour rechercher toutes
les occurre nces incrimi nées.
Hors-série n° 52. Mathématiques & informatique Tangente
lettre), é lé me nt ne utre pour la concaténation. Plusieurs opérations peuvent être
effectuées sur les langages. Si Let L'
sont deux langages, on peut définir L U L'
l' union (a u se n s de la th éo ri e des
ensemb les) des deux langages. LL' est
par définition le langage formé par les
mots qui so nt les concaténations des
mots de L avec les mots de L' . Ainsi,
LL' = {uv, avec u dans Let v dans L'}.
Ensuite, l'étoile de Kleene L * de Lest
le lan gage défin i par {E}U LULL U ...
Enfin , L c est le complémentaire d u langage L (c'est l'ense mbl e des mots fin is
qui apparti e nnent à A * mai s pas à L).
Amusons-nous sur un exemple .
Le langage {aa + b} * contient par exemple
aab o u bbaa mais pas ab. S aurez-vous
le démontrer à l'a ide d ' un rai sonne ment
rigoureux ?
Parmi tou s les langages co ncevables ,
les langages rationn els so nt dé fini s
ains i : pour chaque lettre a da ns A , {a}
est un la ngage ratio nne l ; le complémentaire d'un langage rationnel est un
langage rat ionnel ; l' union ou la concaténation de de ux langages rationnels est
un lan gage ration ne l, et l'étoil e d ' un
langage rationnel est un langage rationnel. On représente généra lement les langages rationnels par des express ion s
rat io nne lles :
• a est l'exp ression rationne lle dé notant
le langage {a} pour une le ttre a apparte na nt à A ,
• e + e' dé note l ' uni o n des la ngages
dénotés par e et e',
• ee' dénote la concaté nati o n des la ngages dé notés par e et e',
• e* dénote l' étoile de Kl eene du la ngage dé noté par e ,
• A *\e dénote le comp lé menta ire du
langage dé noté par e.
Par e xemp le, si o n cons idè re! 'a lphabet
A= {a, b}, le langage des mots fi ni sPOUR L'INFORMATIQUE
Type O
Langages rée. énumérables
Machines de Turing
Type I
Langages contextuels
Automates linéairement bornés
Type 2
Langages algébriques
Automates à pile
La hiérarchie de Chomsky est une classification des langages
formels et des grammaires formelles. Les automates finis
reconnaissent les langages rationnels tandis que les machines
de Turing peuvent calculer tout ce qui est calculable.
sant pa r ab est dé noté par A *ab et le
langage des mots com me nça nt par b,
fm issant par b et ne contenant jamais deux
a conséc utifs est dé noté par
b(ab + b) *, s ig nifi ant : « d ' abord, un b ,
sui vi d ' un nombre arb itra ire de mots
parmi ab et b » (convainq uez-vous bien
que nécessai reme nt tout mot ai n si
co nstruit finira par b).
Le langage {a"b" , avec n un e ntier quel -
conque} , qui est s impl eme nt { E, ab,
aabb , aaabbb .. . } , est un exemple célèbre
de langage non rationnel.
Les notations sur les langages rationne ls ne sont pas sans rappeler les expressions régulières : lorsque je veux vérifier
da ns cet art ic le que je n 'a i pas commen cé un paragraphe par un e lettre
minuscule , mon éd iteur de texte me
permet d ' utili ser l'express ion rég uliè re
\n[a-z], qui correspond à un caractère
de retour de lig ne (newline) su ivi d ' une
lettre minuscule , pour rechercher toutes
les occurre nces incrimi nées.
Hors-série n° 52. Mathématiques & informatique Tangente