Ministerul Educaiei al Republicii Moldova
Universitatea Tehnic a Moldovei
Departamentul Informatica si Ingineria sistemelor
Raport
Lucrarea de laborator 3
La disciplina Limbaje formale i automate
Tema: Forma Normal Chomsky (FNC)
A efectuat: st. gr. MI-161, Busmachiu Cristina
A verificat: [Link].,[Link] Galina
Chiinu 2017
1
Sarcina lucrrii
Aducei gramatica regulat la Forma Normal Chomsky. Etape:
1. Eliminai producii
2. Eliminai redenumirile
3. Eliminai simbolurile inaccesibile
4. Eliminai simbolurile neproductive
5. Aducei la Forma Normal Chomsky
G=(VN, VT, P, S) VN=S, A, B, C, D, E VT=a, b
P=
1. SaB
2. SAC
3. Aa
4. AASC
5. ABC
6. AaD
7. Bb
8. BbS
9. C
10. CBA
11. EaB
12. DabC
1. Eliminm producii:
a) =
b) pentru producia C = {}
P'=
1. SaB
2. SAC 12. SA
3. Aa
4. AASC 13. AAS
5. ABC 14. AB
6. AaD
7. Bb
8. BbS
9. CBA
10. EaB
11. DabC 15. Dab
2
2. Eliminm redenumirile:
O producie de forma XY, X i Y neterminale, se numete redenumire.
Redenumirile din P' sunt: SA, AB
= {}, = {}, = {}
pentru SA = = {} {} = {, }
pentru AB = = {} {, } = {, , }
P''=
1. SaB
2. SAC
3. Aa 14. Sa
4. AASC 15. SASC
5. ABC 16. SBC
6. AaD 17. SaD
7. Bb 18. Ab 21. Sb
8. BbS 19. AbS 22. SbS
9. CBA
10. EaB
11. DabC
12. AAS 20. SAS
13. Dab
3. Eliminm simbolurile inaccesibile:
Iniial ACCES() = {}
ACCES() = {| }
INACCES() = ( )()
ACCES(G)={S, A, B, C, D, a, b}
= {, , , , , }, = {, }
INACCES() = {, , , , , , , , }{, , , , , ,
= {}
P'''=
1. SaB
2. SAC
3. Aa
4. AASC
5. ABC
6. AaD
7. Bb
3
8. BbS
9. CBA
10. DabC
11. AAS
12. Dab
13. Sa
14. SASC
15. SBC
16. SaD
17. Ab
18. AbS
19. SAS
20. Sb
21. SbS
4. Eliminm simbolurile neproductive:
PROD() = {| , , }
NEPROD() = ()
= {, , , , }, = {, }
PROD() = {, , , , }
NEPROD() = {, , , , }{, , , ,
=
PIV=
1. SaB
2. SAC
3. Aa
4. AASC
5. ABC
6. AaD
7. Bb
8. BbS
9. CBA
10. DabC
11. AAS
12. Dab
13. Sa
14. SASC
15. SBC
16. SaD
17. Ab
18. AbS
19. SAS
20. Ab
21. SbS
5. Aducem la Forma Normal Chomsky
O gramatic n forma normal Chomsky este o gramatic cu reguli de forma A BC,
Di, unde A,B,C,DVN i i VT
PIV=
1. Xa
2. Yb
3. SXB
4. SAC
5. Aa
6. AAZ1 23. Z1SC
7. ABC
8. AXD
9. Bb
10. BYS
11. CBA
12. DXZ2 24. Z2YC
13. AAS
14. DXY
15. Sa
16. SAZ1
17. SBC
18. SXD
19. Ab
20. AYS
21. SAS
22. Ab
23. SYS
5
6. Codul surs al programului n C:
#include <stdio.h>
#include <conio.h>
#include <string.h>
char Vn[20], Vt[20], P[50][20], StartSimb = 'S', eps = '?';
int nProd = 0;
void afiseaza()
int i, j;
clrscr();
printf("Productiile la etapa curenta sunt:\n");
for(i=0; i<nProd; i++)
printf("%2d. %c->", (i+1), P[i][0]);
for(j=1; j<strlen(P[i]); j++)
printf("%c", P[i][j]);
printf("\n");
getch();
void citeste()
clrscr();
6
strcpy(Vn, "SABCDE");
strcpy(Vt, "ab");
StartSimb = 'S';
eps = '?';
strcpy(P[0], "SaB");
strcpy(P[1], "SAC");
strcpy(P[2], "Aa");
strcpy(P[3], "AASC");
strcpy(P[4], "ABC");
strcpy(P[5], "AaD");
strcpy(P[6], "Bb");
strcpy(P[7], "BbS");
strcpy(P[8], "C?");
strcpy(P[9], "CBA");
strcpy(P[10], "EaB");
strcpy(P[11], "DabC");
nProd = 12;
afiseaza();
void removeProd(int i) {
printf("Eliminarea productiei %d.\n", (i+1));
for(i; i<nProd; i++)
strcpy(P[i], P[i+1]);
nProd--;
int removeDuplicates() {
int i, j, rem = 0;
7
for(i=0; i<nProd; i++)
for(j=i+1; j<nProd; j++)
if(!strcmp(P[i], P[j]))
removeProd(j);
rem++;
return rem;
void remCharPos(char str[], int j)
for(j; j<strlen(str); j++)
str[j] = str[j+1];
str[j] = '\0';
void epsProd(char c)
int i, j;
for(i=0; i<nProd; i++)
for(j=1; j<strlen(P[i]); j++)
if(P[i][j] == c) {
strcpy(P[nProd], P[i]);
remCharPos(P[nProd], j);
nProd++;
8
void epsilon()
int i,n;
clrscr();
printf("Eliminam epsilon productii:\n");
n=nProd;
for(i=0; i<n; i++)
if(P[i][1] == eps) {
printf("%c->%c\n", P[i][0], eps);
epsProd(P[i][0]);
removeProd(i);
while(removeDuplicates()) ;
getch();
afiseaza();
void redenumiri()
int i, j, k, nrd=0;
char redenumiri[30][10] = {'\0'}, rd[50][3] = {'\0'};
clrscr();
printf("Eliminam redenumirile:\n");
for(i=0; i<strlen(Vn); i++)
redenumiri[Vn[i]-'A'][0] = Vn[i];
9
for(i=0; i<nProd; i++)
if(strlen(P[i]) == 2 && strchr(Vn, P[i][1]) != NULL)
printf("%c->%c\n", P[i][0], P[i][1]);
strcat(redenumiri[P[i][1]-'A'], redenumiri[P[i][0]-'A']);
removeProd(i--);
printf("\nRedenumiri:\n");
for(i=0; i<30; i++)
if(strlen(redenumiri[i]))
printf("%s\n", redenumiri[i]);
for(i=0; i<30; i++)
if(strlen(redenumiri[i]) > 1)
for(j=0; j<strlen(redenumiri[i])-1; j++)
for(k=j+1; k<strlen(redenumiri[i]); k++)
rd[nrd][0] = redenumiri[i][j];
rd[nrd][1] = redenumiri[i][k];
nrd++;
for(i=0; i<nProd; i++)
for(j=0; j<nrd; j++)
if(P[i][0] == rd[j][0])
10
strcpy(P[nProd], P[i]);
P[nProd][0] = rd[j][1];
nProd++;
while(removeDuplicates()) ;
getch();
afiseaza();
void remCharC(char str[], char c)
int i;
for(i=0; i<strlen(str); i++)
if(str[i] == c)
remCharPos(str, i--);
void inaccesibile()
int i, j;
char inaccesibil[20];
strcpy(inaccesibil, Vn);
strcat(inaccesibil, Vt);
remCharC(inaccesibil, StartSimb);
clrscr();
printf("Eliminam simbolurile inaccesibile:\n");
11
for(i=0; i<nProd; i++)
if(P[i][0] == StartSimb)
for(j=1; j<strlen(P[i]); j++)
remCharC(inaccesibil, P[i][j]);
printf("Inaccesibile: %s\n", inaccesibil);
getch();
void fnc()
int main() {
citeste();
epsilon();
redenumiri();
inaccesibile();
return 0;
7. Concluzie
n laboratorul dat s-a fcut cunotin cu etapele de transformare a unei gramatici
regulate pentru a obine Forma Normal Chomsky (FNC). Pentru a obine FNC s-
au eliminat produciile epsilon, redenumirile-(O producie de forma XY, X i Y
neterminale, se numete redenumire).S-a eliminat simbolurile neproductive i
inaccesibile(Iniial ACCES() = {}),aducem la Forma Normala Chomsky (O
gramatic n forma normal Chomsky este o gramatic cu reguli de forma A BC,
Di, unde A,B,C,DVN i i VT).
12
13