Théorie des langages TD3

Exercice 1 : Langage versus Automate minimal

Question 1)

L = a* b*

Etape 0 :	L0 = L = a* b*

Rappel :
	• a a* = a+
	• a* = a+ U ε
	• a-1 a = ε
• a-1 L = Ø avec L ne commençant pas par a

Etape 1 :	a-1 L0 = a-1 a* b*
		          = a-1 (a+ U ε) b*
		          = a-1 a+ b* U a-1 ε b*
		          = a-1 a a* b* U a-1 b*
		          = a* b* U Ø = a* b* = L0

		b-1 L0 = b-1 a* b*
			= b-1 a+ b* U b-1 ε b*
			= b-1 b*
			= b-1 b+ U b-1 ε
			= b-1 b b* U Ø
			= b* = L1

Etape 2 :	a-1 L1 = a-1 b* = Ø = L2
		b-1 L1 = b-1 b* = b* = L1

Etape 3 :	a-1 L2 = a-1 Ø = Ø = L2
		b-1 L2 = b-1 Ø = Ø = L2

Les états finaux sont les états dont les sous-langages associés contiennent ε.

a

b

 L2

L1

L0

b

a

a,b

Exercice 2 : Automate versus Langage

Question 1)

XP = 0XP + 1XI + ε (car P état final)		(1)
XI = 0XI + 1XP				(2)

Le but : trouver l’inconnue associée à l’état initial
•	C’est L (ici XP)

Lemme d’Arden
	X = BX + C
•	X = B*C si ε n’appartient pas à B
X = B+C sinon

(2)	XI = 0XI + 1XP
	XI = 0* 1 XP

(1)	XP = 0XP + 1 0* 1 XI + ε
	XP = (0 + 1 0* 1)XP + ε
	XP = (0 + 1 0* 1)* ε
	XP = (0 + 1 0* 1)*

Donc L = (0 + 1 0* 1)*

Prenons l’exo 1 et on fait le lemme d’Arden

X0 = aX0 + bX1 + ε			(1)
X1 = bX1 + aX2 + ε			(2)
X2 = (a + b)X2				(3)

(3)	X2 = (a + b)X2	 + Ø
	X2 = (a + b)* Ø = Ø

(2)	X1 = bX1 + ε
	X1 = b*ε = b*

(1)	X0 = aX0 + bb* + ε
	X0 = aX0 + b+ + ε
	      = aX0 + b*
	      = a* b*

Donc L = a* b*