Grammaire greibach et chomsky

5 ans après mais ça peut toujours aider ^^
alors il faut rendre la grammaire propre c'est à dire : sans cycle (pas de productions du genre A->A), epsilon libre (on doit pas avoir une production du genre A->mot_vide, sauf dans l'axiom S et S ne doit pas apparaitre dans un membre droit), réduite (supprimer les productions innaccessibles et les productions non productives) ;
on supprime les enchainements de variables (on remplace); et on la met sous FNC (forme normale de chomsky)
pour l'exemple du Mr;
P={S -> aABAC, A -> C, A->mot vide, B -> A, B -> aaa, B -> C, C -> A, C -> aaBB}
P devient :
S->aABAC
A->C/£ =>on remplace ttes les productions de A par £
B->A/aaa/C
C->A/aaBB
alors
S->aBAC/aABC/aBC
A->C
B->£/A/aaa/C
C->£/A/aaB
on a le mot vide £ dans B et C ; on remplace tt les B et C par £
S->aBAC/aABC/aBC/aAC/aC/aBA/aB/aA/a
A->C
B->A/aaa/C
C->A/aaB/aa
on supprime l'enchainement de variable :
on remplace C dans A
A->A/aaB/aa et on supprime le cycle A->A
A->aaB/aa
on remplace C et A dans B :
B->aaB/aa/aaa/aaB/aa
C->aaB/aa

P devient :
S->aBAC/aABC/aBC/aAC/aC/aBA/aB/aA/a
A->aaB/aa
B->aaB/aa/aaa/aaB/aa
C->aaB/aa

on la met mntn sous FNC c'est à dire :
"A->BC A,B,C sont des variables, ou A->x x est une lettre"
ici il suffit de remplacer les terminaux par une variable, et chaque deux variables par une nouvelle variable ... ^^

bjrs avous , vous vous etes tromper de forum.
ici : forum informatique
la bas : forum etudiants