Université Bordeaux I Licence Informatique TD OMI 2001
Feuille d'exercices 1 Corrigé de l'exercice 12
Preuve par induction sur la longueur des mots: on
suppose l'égalité vraie pour tout mot de longueur
inférieure à n.
- L'égalité est vraie pour les mots de longueur 1.
- Soit w un mot de longueur n et soit x
la lettre de X telle
que w=xu, alors:
delta((q1,q2),w)
=
delta((q1,q2),xu)
=
delta(delta((q1,q2),x)u)
=
delta((delta1(q1,x),delta2(q2,x)),u)
Soient q'1=delta1(q1,x) et q'2=delta2(q2,x), on a
donc, par hypothèse (car |u|<n):
delta((q'1,q'2),u)
=
(delta1(q'1,u),delta2(q'2,u))
=
(delta1(delta1(q1,x),u),delta2(delta2(q2,x),u))
=
(delta1(q1,xu),delta2(q2,xu))
Intersection: les états terminaux sont les couples
(q1,q2) avec q1 état terminal de
A1 et q2 état terminal de
A2: on reconnait ainsi les
mots reconnus soit par A1 que
par A2.
Union: états terminaux sont les couples
(q1,q2) avec q1 état terminal de
A1 ou (non exclusif!) q2 état terminal de
A2: on reconnait ainsi les
mots reconnus par au moins l'un des deux
automates A1 et A2.
L'intersection et l'union de langages reconnaissables
sont donc des langages reconnaissables.