"Si considerino le grammatiche $G1=<{a,b,c},{S,A},S,P>$ in cui le produzioni sono: $S:= aSc|A ;A := bAc|epsilon$ e $G2=<{a,b,c},{S,A},S,P>$ in cui le produzioni sono: $S:= Sc|A ;A:= aA|B; B:= bB|b$, scrivere i linguaggi L1 e L2 generati rispettivamente da G1 e G2 e implementare in C una o più funzioni ricorsive che dato un array v di caratteri alfabetici minuscoli e la sua dimensione dim controllino se la sequenza contenuta nell’array appartiene o meno al linguaggio generato dalla grammatica G1/G2."
Allora io ho fatto tutto...volevo un vostro parere. Cominciamo:
Il linguaggio L1 dovrebbe essere $L1={a^kb^hc^(h+k)|h,k>=0}$, mentre $L2={a^xb^yc^z|x>=0,y>0,z>=0}$
Ho poi implementato le seguenti:
- Codice:
bool checkA(char a[],int dim){
if(dim<=0) return true;
else if(dim%2!=0) return false;
else if(a[0]=='b' && a[dim-1]=='c') return checkA(a+1,dim-2);
else return false;
}
bool checkS(char a[],int dim){
if(dim<=0) return true;
else if(dim%2!=0) return false;
else if(a[0]!='a') return checkA(a,dim);
else if(a[0]=='a'&& a[dim-1]=='c') return checkS(a+1,dim-2);
else return false;
}
Per la seconda, invece, questa:
- Codice:
bool checkallA(char v[],int dim){
if(dim<=0) return true;
else if(v[dim-1]!='a') return false;
else return checkallA(v,dim-1);
}
bool checkB(char v[],int dim){
if(dim<=0) return true;
else if(v[0]!='b') return false;
else return checkB(v,dim-1);
}
bool checkA(char v[],int dim){
if(dim<=0) return true;
else if(v[dim-1]=='b'&& v[0]=='a') return checkA(v,dim-1);
else if(v[dim-1]=='b' && v[0]=='b') return checkB(v,dim-1);
else if(v[dim-1]=='a') return checkallA(v,dim-1);
else return false;
}
bool checkS(char v[],int dim){
if(dim<=0) return false;
else if(v[dim-1]=='c') return checkS(v,dim-1);
else if(v[dim-1]=='a') return false;
else if(v[dim-1]=='b' && v[0]=='b') return checkB(v,dim-1);
else if(v[dim-1]=='b' && v[0]=='a') return checkA(v,dim-1);
else return false;
}
Diciamo che non sono proprio per l'ottimizzazione xD. A parte gli scherzi meglio di questo non mi è venuto niente altro...
Mi scuso per la lunghezza (e l'indentazione) e grazie in anticipo a chi vorrà collaborare
