Question – Trtouver le langage reconnu par l'automate ci-dessous:

Réponses

En regardant l'automate est en raisonnat un peu, on s'apperçoit qu'il s'agit des mots sur V = {a, b} tels que le nombre de "a" est pair et que le nombre de "b"' est aussi pair. Ce qui peut s'écrire:

Essayons de trouver l'expression régulière de ce langage.

Méthodes des équations :

(1)  L0 = aL1 + bL2 + eps
(2)  L1 = aL0 + bL3
(3)  L2 = aL3 + bL0
(4)  L3 = aL2 + bL1

Essayons d'obtenir L0 en fonction de lui-même. Si dans (3) on remplace L3 par (4) :

(5)  L2 = a(aL2 + bL1) + bL0
(6)  L2 = aaL2 + abL1 + bL0

on résoud L2

(7)  L2 = (aa)*(abL1 + bL0)

Si dans (4) on remplace L2 par (7)

(8)  L3 = a(aa)*(abL1 + bL0) + bL1

Si dans (2) on remplace L3 par (8)

(9)  L1 = aL0 + b(a(aa)*(abL1 + bL0) + bL1)
(10) L1 = aL0 + ba(aa)*(abL1 + bL0) + bbL1
(11) L1 = (ba(aa)* ab + bb)L1 + (a + ba(aa)*b)L0

on résoud L1

(12) L1 = (ba(aa)* ab + bb)*(a + ba(aa)*b)L0

Simplifions on peu (12). On remarque que ba(aa)* ab + bb = b(aa)*b donc

     L1 = (b(aa)*b)*(a + ba(aa)*b)L0
     L1 = ( (b(aa)*b)*a + (b(aa)*b)*ba(aa)*b )L0
     L1 = ( (b(aa)*b)*a + (b(aa)*b)*b(aa)*ab )L0
     L1 = ( (b(aa)*b)*a + b(aa)*(bb(aa)*)*ab )L0
(12') L1 = ( (b(aa)*b)*a + b(aa+bb)*ab )L0

Si dans (7) on remplace L1 par (12')

(13) L2 = (aa)*(ab( (b(aa)*b)*a + b(aa+bb)*ab )L0 + bL0)
(14) L2 = (aa)*(ab( (b(aa)*b)*a + b(aa+bb)*ab ) + b)L0

Simplifions on peu (14). On distribue

     L2 = ( (aa)*ab( (b(aa)*b)*a + b(aa+bb)*ab ) + (aa)*b)L0
     L2 = ( (aa)*ab (b(aa)*b)*a + (aa)*abb(aa+bb)*ab + (aa)*b )L0
     L2 = ( a(aa)*b(b(aa)*b)*a + (aa)*abb(aa+bb)*ab + (aa)*b )L0
     L2 = ( a((aa)*bb)(aa)*ba +(aa)*abb(aa+bb)*ab + (aa)*b )L0
(14') L2 = ( a(aa+bb)*ba + (aa)*abb(aa+bb)*ab + (aa)*b )L0

Si dans (1) on remplace L1 par (12') et L2 par (14')

(15) L0 = a( (b(aa)*b)*a + b(aa+bb)*ab )L0 + b ( a(aa+bb)*ba + (aa)*abb(aa+bb)*ab + (aa)*b )L0 + eps
(16) L0 = ( a(b(aa)*b)*a + ab(aa+bb)*ab + ba(aa+bb)*ba + b(aa)*abb(aa+bb)*ab + b(aa)*b )L0 + eps

on résoud L1

(17) L0 = ( a(b(aa)*b)*a + ab(aa+bb)*ab + ba(aa+bb)*ba + b(aa)*abb(aa+bb)*ab + b(aa)*b )*

Simplifions un peu (17). Nommons les termes : L0 = (#1 + #2 + #3 + #4 + #5)*

b(aa)*abb(aa+bb)*ab =

ba(aa)*bb((aa)*bb)*(aa)*ab + b(aa)*abb(bb)*(aa(bb)*)*ab

a(b(aa)*b)*a = a(bb)*a + a(b(aa)*b)*a