Université Bordeaux I
Licence Informatique TD OMI 2001


Feuille d'exercices 3
Corrigé de l'exercice 3




  1. X0 = B*L est une solution de X = BX + L:
    B*L = BB*L + L = (BB* + epsilon)L = B*L
    C'est la plus petite solution: soit Y une autre solution, plus petite de X0, alors Y est un sous-ensemble de B*L et Y = BY + L et donc (en substituant BY + L à Y):
    Y = B2Y + BL + L = B3Y + B2L + BL + L = ... = BnY + Bn-1L + ... + L.
    On a BnL sous-ensemble de Y, pour tout n dans IN et donc B*L est sous-ensemble de Y. Mais on a aussi supposé Y sous-ensemble de B*L et donc Y = B*L.

  2. Soit Y une autre solution. B*L est la plus petite solution, donc B*L sous-ensemble de Y. On a vu que:
    Y = Bn+1Y + BnL + Bn-1L + ... + BL + L. Soit w un mot de Y avec |w| = n, alors compte tenu que B ne contient pas epsilon, w est dans BnL + Bn-1L + ... + BL + L et donc w appartient à B*L.

  3. L'automate reconnaissant L est:
       

       
    Si l'on pose Li = {u dans {a,b}*tels que delta*(i,u)= 4 }, on a L = L1.
    On a donc le système:
    L1 = aL2 + bL4
    L2 = aL1 + bL3
    L3 = aL4 + bL2
    L4 = aL3 + bL1 + epsilon

    Qu'on résoud par rapport à L1:
    L1 = a2L1 + abL3 + baL3 + b2L1 + b
      = (a2 + b2)L1 + (ab + ba)L3 + b
    L3 = a2L3 + abL1 + a + baL1 + b2L3
      = (a2 + b2)L3 + (ab + ba)L1 + a
      = (a2 + b2)*((ab + ba)L1 + a)
      = (a2 + b2)*(ab + ba)L1 + (a2 + b2)*a
    L1 = (a2 + b2)L1 + (ab + ba)(a2 + b2)*(ab + ba)L1 + (ab + ba)(a2 + b2)a + b
      = ((a2 + b2) + (ab + ba)(a2 + b2)*(ab + ba))L1 + (ab + ba)(a2 + b2)a) + b
      = ((a2 + b2) + (ab + ba)(a2 + b2)*(ab + ba))* ((ab + ba)(a2 + b2)a + b)





Deuxième façon de prouver le point 1:
On considère l'application f de P(A*) dans P(A*) (où P(A*) désigne l'ensemble des parties de A*) telle que f(X)= BX + L.
P(A*) est un ensemble complet, car un sous-ensemble de P(A*) est une famille de langages qui admet comme borne supérieure l'union.
f est une application continue, il y a donc un plus petit point fixe obtenu par:
^ = Ø
f(^) = f(Ø)= L
f2(^) = f(L)= BL + L
.   .
.   .
.   .
.   .
fn+1(^) = fn+1(^)= BnL + Bn-1L+ ... + BL + L

or sup({fn(^) | n dans IN}) = B*L.
This document was translated from LATEX by HEVEA.