Muni de ces opérations et de
leurs lois, on peut calculer avec les
langages, et obtenir de nouveaux langages.
Certains de ces calculs peuvent être décrits sous la forme
d'expressions
(de même que les expressions algébriques décrivent certains calculs sur
des nombres).
Comme l'expression représente un calcul, on peut lui associer le
résultat de ce calcul, qu'on appelle la valeur de
l'expression.
Précisément, une expression régulière est une
expression de ce type
- où n'interviennent que
les opérations d'union,
produit et étoile
- où le calcul commence à
partir de singletons
d'une seule lettre.
La suite du cours va étudier
la classe des langages qui peuvent être
décrits par des expressions régulières.
Nous pouvons à présent donner un sens précis à cette idée de description
:
il s'agit des langages L pour qui il existe une
expression E telle que L soit la valeur
de E.
Exemple : le langage L = { ab, raca,
dabra } est la
valeur de l'expression
E = {a}{b}
∪ {r}{a}{c}{a}
∪ {d}{a}{b}{r}{a}.
La plupart du temps, on commet l'abus de notation consistant à
assimiler la lettre et le singleton.
En notation de programmeur, notre expression s'écrit alors :
E = ab|raca|dabra.
Exemple : Étude d'une égalité
yx*xy*x (notre
calcul) = yxxx* | yxyy*x | yxxx*yy*x
(calcul de la machine)
Manipulation
qui est à l'origine de cette égalité
Reprenons-la et voyons ce qu'elle nous dit.
-
La barre verticale est
ici le symbole de la réunion ensembliste.
Notre égalité s'écrit en notation des mathématiciens :
yx*xy*x
= yxxx* ∪ yxyy*x ∪ yxxx*yy*x
Posons A = yx*xy*x
, B = yxxx*, C = yxyy*x,
et D = yxxx*yy*x.
Elle devient A = B∪C∪D.
-
- B∩C
= ∅
car la troisième lettre d'un mot ∈B doit être x,
alors que la troisième lettre d'un mot ∈C
doit être y.
- B∩D
= ∅
car un mot ∈B ne contient qu'un seul y (à
l'initiale), alors qu'un mot ∈D en contient
au moins deux (à la pénultième).
- C∩D
= ∅
car la troisième lettre d'un mot ∈C doit
être y, alors
que la troisième lettre d'un mot ∈D doit
être x.
-
- B⊆A
Les mots ∈B sont ceux de A pour
lesquels on a choisi un nombre nul de y
comme contribution du facteur y*.
En effet, avec cette hypothèse on obtient le sous-ensemble yx*xx,
qui est égal à B puisque x*x
= xx*,
c'est à dire l'ensemble { xn
| n > 0 }.
- C⊆A
Les mots ∈C sont ceux de A pour
lesquels on a choisi un nombre non nul de y
comme contribution du facteur y*,
et un nombre nul de x
comme contribution du facteur x*.
En effet, avec ces hypothèses on obtient le sous-ensemble yxyy*x,
qui est C,
- D⊆A
Les mots ∈D sont ceux de A pour
lesquels on a choisi un nombre non nul de y
comme contribution du facteur y*,
et un nombre non nul de x
comme contribution du facteur x*.
En effet, avec ces hypothèses on obtient le sous-ensemble yxx*xyy*x,
qui est égal à D
puisque x*x = xx*.
Il s'ensuit que A ⊇ B∪C∪D.
-
Les éléments de A
sont tous de la forme
yxnypx
, avec n > 0 (à cause de x*x)
et p >= 0.
En notation ensembliste A = { yxnypx
| n > 0, p
>= 0 }.
Dans cette configuration, on peut distinguer trois cas qui épuisent les
possibilités :
- p = 0, qui
correspond à B
= {
yxnx
| n > 0 }
- p > 0
et n
= 1, qui correspond à C = {
yxypx
| p > 0 }
- p > 0
et n
> 1, qui correspond à D = {
yxnypx
| n > 1, p
> 0 }
Il s'ensuit que A ⊆ B∪C∪D.
-
A ⊇ B∪C∪D
et A ⊆ B∪C∪D
nous pouvons déduire l'égalité recherchée :
A = B∪C∪D.
Quod erat demonstrandum.
Ajoutons que, puisque les trois sous-ensembles sont disjoints, nous
avons affaire à une partition de A.
Sur cette notion importantissime nous reviendrons plus tard.