Université Bordeaux I
Licence Informatique TD OMI 2001


Feuille d'exercices 1
Corrigé de l'exercice 12



  1. 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))

  2. L'intersection et l'union de langages reconnaissables sont donc des langages reconnaissables.

This document was translated from LATEX by HEVEA.