Théorie des langages TD Révisions

•	CKY :

Phrase préliminaire : trouver la grammaire du langage sous forme normale de Chomsky
A -> a avec a Є T
A -> BC avec B, C Є N

L = a*b+c			mot = aaabc

G = {	T = {a, b, c}
N = {mot, A, B}
S = mot
P = {mot -> Abc
A -> ε | aA
B -> b | bB
}
}

Pas sous forme normale de Chomsky (Abc, aA, bB)

A1 -> a
B1 -> b
C1 -> c
Mot -> ABC1
A -> ε | A1A | a
B -> b | B1B

Mot -> AD
D -> BC1

a	A1,A	A	A	mot	mot	
a	A1,A	A	Ø	mot		
a	A1,A	Ø	mot			
b	B1,B	D				
c	C1					

Le mot est reconnu.

•	Quotients Gauches :

L -> A

L = a*b+c

Etape 0 : L0 = L = a*b+c
Etape 1 : a-1L0 = a-1a*b+c
		= a-1a+b+c U a-1b+c
		= a-1aa*b+c = a*b+c = L0
b-1L0 = b-1a*b+c
	= b-1a+b+c U b-1b+c
	= b*c = L1

c-1L0 = c-1a*b+c
	= Ø = L2

Etape 2 : a-1L2 = b-1L2 = c-1L2 = Ø = L2

Etape 3 : a-1L1 = a-1b*c = Ø = L2
	    b-1L1 = b-1b*c = … = b*c = L1
	    c-1L1 = c-1b*c = c-1b+c U c-1c = ε = L3

Etape 4 : a-1L3 = a-1ε = Ø = L2
	    b-1L3 = c-1L3 = Ø = L2

•	Lemme d’Arden :

A -> L

X0 -> aX0 + bX1	(1)
X1 -> bX1 + cX3	(2)
X3 -> ε			(3)

But : Trouver X0 = L

(2) 	X1 -> bX1 + c
	X1 -> b*c	(d’après le lemme)

Dans (1)	X0 -> aX0 + bb*c
		X0 -> aX0 + b+c

Lemme : 	X0 -> a*b+c

	L = a*b+c

•	Déterminisation :

•	Automate à pile :

L = (n c+ )n	Rmq : on peut mettre des caractères à la place des lettres, ici des « ( ) ».