Théorie des Langages - 5
vendredi 9 mai 2014
10:59
Mise en forme normale de Chomsky:
Données: Une grammaire de type 2
Question: Trouver une grammaire en forme normale de Chomsky équivalente 
i.e dont toutes règles sont de la forme:
A -> a (un terminal)
A -> BC (deux non-terminaux)
Etape 1:
On ajoute les deux règles suivantes:
A1 -> a
B1 -> b
Etape 2:
A -> b(AA)
B -> a(BB)
A2 -> AA (A2 est donc le langage des mots ayant deux b de plus)
B2 -> BB (etc)
Etape 3:
Réecrire la grammaire avec les règles ajoutées:
(1') S -> B1 A
(2') S -> A1 B1
(3') A  -> B1 A2
(4') A -> A1 S
(5') A -> a
(6') B -> A1 B2
(7') B -> B1 S
(8') B -> b
(9') A1 -> a
(10') B1 -> b
(11') A2 -> AA
(12') B2 -> BB
Données: Grammaire G de type 2 et un mot w
Question: w appartient-il à L(G)?
T={a,b}  Elements du langage (Terminaux)
N= {S,A,B} Elements groupant d'autres (Non-terminaux)
P={ } Possibilités
Définir L(G):
ε = elt vide
L(G) = {ε,a,b,aa,ab,ba,b,aaa,aab,aba,abb,baa,bab,bba,bbb,aaaa,abba,baab,...}
Dans L
Pas dans L
On peut en déduire que: 
Le résultat est bien sous forme normale de Chomsky équivalente.
Sous-mot
Taille 6
S
(a1a2b3b4a5b6)
S -> A1 B
Sous-mot
Taille 5
A(4')
(a1a2b3b4a5)
B
(a2b3b4a5b6)
B -> A1 B2
Sous-mot
Taille 4
S(2')
(a1a2b3b4)
S(2')
(a2b3b4a5)
B2(12')
(b3b4a5b6)
B2 -> B B
Sous-mot
Taille 3
A(règle 4')
(a1a2b3)
B(règle 6')
(a2b3b4)
B(règle 7')
(b3b4a5)
B(règle 7')
(b4a5b6)
B -> B1 S
Sous-mot 
Taille 2
A2(règle 11')
(a1a2)
S(règle 2')
(a2b3)
B2(règle 12')
(b3b4)
S(règle 1')
(b4b5)
S(règle 2')
(a5b6)
S -> A1 B
Sous-mot 
Taille 1
A,A1
(a1)
A,A1
(a2)
B,B1
(b3)
B,B1
(b4)
A,A1
(a5)
B,B1
(b6)
a1
a2
b3
b4
a5
b6
(a1a2b3) = a1(a2 b3) OU (a1 a2) b3
      = A,A1 S OU A B,B1
(a1a2b3b4) = a1(a2b3b4) OU (a1a2)(b3b4) 
                        OU (a1a2b3) b4
Etc.