Théorème du produit cartésien
Soient L1 et L2 deux langages reconnaissables alors le produit cartésien de L1 par L2, noté L1 × L2, est reconnaissable.
Autrement dit, si L1 ∈ Rec(A*) et L2 ∈ Rec(A*) alors L1 × L2 ∈ Rec(A*).
Dans les sections précédentes, nous avons présenté des algorithmes pour optimiser des automates (déterminisation, minimisation). Dans cette section, nous allons aborder l'application d'opérateurs sur les automates : le produit de deux automates, la mise à l'étoile d'un automate et l'union de deux automates.
Le produit de deux langages permet de construire un langage dont les mots résultent de la concaténation d'un mot du premier langage avec un mot du second langage. Dans le cas des langages reconnaissables, cette opération permet d'obtenir un langage reconnaissable.
|
|
Soient L1 et L2 deux langages reconnaissables alors le produit cartésien de L1 par L2, noté L1 × L2, est reconnaissable. Autrement dit, si L1 ∈ Rec(A*) et L2 ∈ Rec(A*) alors L1 × L2 ∈ Rec(A*). |
Démonstration :
Si les langages L1 et L2 sont reconnaissables alors il existe des automates finis les reconnaissant, notés respectivement T1={A1, Q1, I1, F1, μ1} et T2={A2, Q2, I2, F2, μ2}. Si L1 × L2 est reconnaissable alors il existe aussi un automate fini T={A, Q, I, F, μ}. Il est possible de construire ce dernier. Prenons comme hypothèse que Q1 ∩ Q2 = ∅ (quitte à renommer l'un ou l'autre).
Il est possible de prouver que T reconnait bien le langage L1 × L2 en utilisant les suites d'actions (ou de configurations). Autrement dit, il faut prouver que L(T) = L(T1) × L(T2).
Cette démonstration nous permet de donner un méthode pour construire l'automate résultant du produit cartésien de deux langages reconnaissables. Par abus de langage, nous parlerons du produit (cartésien) de deux automates et ce sera noté T1 × T2.
Pour illustrer cet algorithme, prenons les deux automates suivants :
On obtient dans ce cas :
Remarques :
Dans le cas où T2 est standard, une autre approche du produit (similaire) est une "fusion" entre les états finaux de premier automate et l'état initial du second. L'état initial de T2 est ensuite supprimé par émondage.
Remarque : dans
ce cas, T2 doit absolument être standard donc I2={i2}
(il est toujours possible de le
construire), car il ne faut pas de transitions "retournant" sur
l'état initial de T2. En effet, de la manière où
T est construit, il serait possible de revenir sur T1 et donc de
produire des mots de T1 ! Prenons par exemple les langages L1
et L2 reconnus respectivement par les deux automates dans la figure
suivante :
Le produit par fusion de ces deux automates L = L1 × L2, donne :
L contient des mots comme "aab" qui est bien la concaténation de "a" du premier langage et "ab" dans le second langage. Par contre, L contient aussi "aabbcaab" qui ne peut pas être décomposé en un préfice dans L1 et le reste dans L2 !
La mise à l'étoile d'un langage L, notée L*, est l'ensemble des produits cartésiens d'un langage avec lui-même à l'infini. Dans le cas des langages reconnaissables, cette opération permet d'obtenir un langage reconnaissable.
|
|
Soient L un langage reconnaissable alors la mise à l'étoile de L, notée L*, est reconnaissable. Autrement dit, si L ∈ Rec(A*) alors L* ∈ Rec(A*). |
Démonstration :
Si le langage L est reconnaissable alors il existe un automate fini le reconnaissant, noté T={A, Q, I, F, μ}. Si L* est reconnaissable alors il existe aussi un automate fini T'={A, Q', I', F', μ'}. Il est possible de construire ce dernier. Prenons comme hypothèse que T est standard donc I={i} (il est toujours possible de le construire).
Il est aussi possible de prouver que T reconnaît bien le langage L* en utilisant les suites d'actions (ou de configurations). Autrement dit, on peut montrer que L(T) = L*.
Cette démonstration nous permet de donner un méthode pour construire l'automate résultant de la mise à l'étoile d'un langage reconnaissable. Par abus de langage, nous parlerons de la mise à l'étoile d'un automate et ce sera noté T*.
Pour illustrer cet algorithme, prenons l'automate suivant :
On obtient dans ce cas :
Remarque : T doit
être absolument standard, car il ne faut pas de transitions retournant
sur l'état initial de T. En effet, de la manière où T*
est construit, il serait possible de terminer sur i qui n'était pas final
dans T !
Prenons par exemple le langage L dans la figure suivante :
L reconnait des mots comme "ab", "abbab", "abbabbab"...L'automate n'est pas standard (à cause de la transition (3,b,1)). L* reconnaît bien évidemment ε mais aussi "abb" qui ne peut pas être constitué de concaténations de mots de L ! En effet, les mots les plus courts le L* sont "ε", "ab", "abab", "abbab"...
L'union de deux langages permet de construire un langage dont les mots sont issus soit d'un mot du premier langage soit d'un mot du second langage. Dans le cas des langages reconnaissables, cette opération permet d'obtenir un langage reconnaissable.
|
|
Soient L1 et L2 deux langages reconnaissables alors l'union de L1 et L2, noté L1 ∪ L2, est reconnaissable. Autrement dit, si L1 ∈ Rec(A*) et L2 ∈ Rec(A*) alors L1 ∪ L2 ∈ Rec(A*). |
Démonstration :
Si les langages L1 et L2 sont reconnaissables alors il existe des automates finis les reconnaissant, notés respectivement T1={A1, Q1, I1, F1, μ1} et T2={A2, Q2, I2, F2, μ2}. Si L1 ∪ L2 est reconnaissable alors il existe aussi un automate fini T={A, Q, I, F, μ}. Il est possible de construire ce dernier. Prenons comme hypothèse que Q1 ∩ Q2 = ∅ (quitte à renommer l'un ou l'autre).
Il est assez facile de prouver que T reconnaît bien le langage L1 ∪ L2 en utilisant les suites d'actions (ou de configurations) puisque l'on simule un parcours en parallèle des deux automates.
Cette démonstration nous permet de donner un méthode pour construire l'automate résultant de l'union de deux langages reconnaissables. Par abus de langage, nous parlerons de l'union de deux automates et ce sera noté T1 ∪ T2.
Cette méthode
de construction est très simple mais possède un inconvénient
considérable : même si les deux automates de départ sont
déterministes, le résultat n'est forcément pas déterministe.
En effet, l'automate union possède toujours au moins deux états
initiaux (I = I1 ∪ I2) !
Il existe une autre méthode pour construire l'automate union pour qu'à partir de deux automates déterministe, cet automate union soit, lui aussi, déterministe. Soit T1={A1, Q1, I1, F1, μ1} et T2={A2, Q2, I2, F2, μ2} deux automates déterministes et complets. T = T1 ∪ T2 = {A1 ∪ A2, Q1 × Q2, {(i1,i2)}, (F1 × Q2) ∪ (Q1 × F2), μ} avec μ = {((p1,p2),a,(q1,q2)) : (p1,a,q1) ∈ μ1 et (p2,a,q2) ∈ μ2}. Autrement dit, on construit un automate dont les états sont tous les couples possibles d'états entre T1 et T2 et les états finaux sont ceux ayant un état final de T1 ou de T2 . L'état initial est le couple des états initiaux des deux automates. Il n'y en a qu'un puisqu'ils sont déterministes.
Cette dernière méthode propose bien un automate déterministe et complet mais celui ci possède un très grand nombre d'états (|Q1| × |Q2|) dont un grand nombre est inutile (pas accessibles et/ou co-accessibles).
Il est cependant possible d'améliorer cet algorithme en ne construisant que des états accessibles. Pour cela, il suffit d'adapter la méthode utilisée pour rendre déterministe un AFN, c'est-à-dire l'algorithme par construction des sous-ensembles. Considérons T1 et T2 deux automates déterministes émondés (c'est toujours possible). L'état de départ est l'état composé du couple des états initiaux. Ensuite, pour chaque état créé (p1,p2), et chaque symbole a de l'alphabet :
Cet algorithme construit un automate déterministe dont les états sont accessibles mais pas forcément co-accessibles. Il est nécessaire de le minimiser ensuite.
Pour illustrer cet algorithme, prenons les deux automates suivants :
L'algorithme de construction permet d'obtenir le tableau suivant :
a |
b |
c |
|
1,5 ∈ I |
2,6 |
0,6 |
0,0 |
2,6 |
2,0 |
3,7 |
0,0 |
0,6 |
0,0 |
0,7 |
0,0 |
2,0 |
2,0 |
3,0 |
0,0 |
3,7 ∈ F |
2,8 |
0,0 |
4,0 |
0,7 ∈ F |
0,8 |
0,0 |
0,0 |
3,0 ∈ F |
2,0 |
0,0 |
4,0 |
2,8 |
2,8 |
3,7 |
0,0 |
4,0 ∈ F |
0,0 |
0,0 |
0,0 |
0,8 |
0,8 |
0,7 |
0,0 |
On obtient dans ce cas (image issue de JFLAP) :
Après minimisation (comme quoi c'est nécessaire !), on obtient :
Une conséquence de ce théorème de l'union est le théorème suivant :
|
|
Avant de démontrer ce théorème, démontrons d'abord le lemme suivant :
|
|
Démonstration du lemme :
L'automate permettant de reconnaître un unique mot x = a1a2...an se construit avec n+1 états noté de 1 à n+1, 1 est l'état initial, n+1 l'état final et les transitions ∀ i ∈ [1..n], μ(ai,n)=n+1.
Démonstration du théorème :
Un langage fini possède un nombre fini de mots, soit m ce nombre. Ce langage peut donc être construit comme étant l'union de m langages réduits à un seul mot. Or, par le lemme précédent, chacun de ces langages est reconnaissable et, de plus, l'union de langages reconnaissables est reconnaissable. CQFD
Exercices et tests :
Exercice 10.1. Démontrer le théorème suivant :
|
|
Soient L un langage reconnaissable alors le complémentaire de L, noté Comp(L), est reconnaissable. Autrement dit, si L ∈ Rec(A*) alors Comp(L) ∈ Rec(A*). |
En déduire une méthode pour construire l'automate "complémentaire" d'un automate.
Appliquer la méthode sur l'automate suivant : 
Exercice 10.2. Démontrer le théorème suivant :
|
|
Soient L1 et L2 deux langages reconnaissables alors l'intersection de L1 et L2, noté L1 ∩ L2, est reconnaissable. Autrement dit, si L1 ∈ Rec(A*) et L2 ∈ Rec(A*) alors L1 ∩ L2 ∈ Rec(A*). |
En déduire une méthode pour construire l'automate issu de "l'intersection" de deux automates. Faites en sorte qu'il soit déterministe si les deux automates de départ le sont.
Appliquer la méthode sur les automates suivants :
Exercice 10.3.Soit L en langage et a1a2...an un mot de L alors le transposé de L, noté L-1 contiendra le mot an...a2a1. Démontrer le théorème suivant :
|
|
Soient L un langage reconnaissable alors le transposé de L, noté L-1, est reconnaissable. Autrement dit, si L ∈ Rec(A*) alors L-1 ∈ Rec(A*). |
En déduire une méthode pour construire l'automate "transposé" d'un automate.
Appliquer la méthode sur l'automate suivant :
|
|
Soient L1 et L2 deux langages reconnaissables alors la différence de L1 et L2, noté L1 - L2 ou L1\L2, est reconnaissable. Autrement dit, si L1 ∈ Rec(A*) et L2 ∈ Rec(A*) alors L1\L2 ∈ Rec(A*). |
En déduire une méthode pour construire l'automate issu de "la différence " de deux automates. Faites en sorte qu'il soit déterministe si les deux automates de départ le sont.
Appliquer la méthode sur les automates suivants :
Exercice 10.5. Soit les automates T1 sur {a,b,c} et T2 sur {a,b,c,d} suivants :
Construire les automates ε-libres suivants (à chaque fois, précisez l'alphabet) :
mercredi, 17/12/03 12:44
