Grammaire greibach et chomsky
Fermé
mousekey
Messages postés
68
Date d'inscription
dimanche 13 février 2005
Statut
Membre
Dernière intervention
22 novembre 2014
-
7 nov. 2005 à 17:13
geek - 4 juin 2010 à 19:19
geek - 4 juin 2010 à 19:19
A voir également:
- Grammaire greibach et chomsky
- Correcteur grammaire - Guide
- Télécharger conjugaison et grammaire - Télécharger - Dictionnaires & Langues
- Règle de grammaire - Guide
- Telecharger correcteur d'orthographe et grammaire gratuit français pdf ✓ - Forum PDF
- [Grammaire] Genre du nom "socket" ? ✓ - Forum Windows
2 réponses
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 ... ^^
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 ... ^^
pvallaud
Messages postés
801
Date d'inscription
dimanche 18 septembre 2005
Statut
Membre
Dernière intervention
18 octobre 2012
77
7 nov. 2005 à 18:36
7 nov. 2005 à 18:36
bjrs avous , vous vous etes tromper de forum.
ici : forum informatique
la bas : forum etudiants
ici : forum informatique
la bas : forum etudiants