Esercizio grammatiche e ricorsione

Messaggioda nick_10 » 14/12/2018, 22:42

Ciao! Sono sempre io alle prese con esercizi su grammatiche e funzioni ricorsive. Il testo recita così:
"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
nick_10
Junior Member
Junior Member
 
Messaggio: 370 di 373
Iscritto il: 17/11/2016, 17:21

Re: Esercizio grammatiche e ricorsione

Messaggioda nick_10 » 15/12/2018, 19:59

Dopo un controllino veloce ho trovato una cosa da sistemare.
Nel secondo codice nel bool checkB nella condizione dell if in cui chiedo che il primo elemento è uguale a b devo scrivere l'utimo perché sto andando a ritroso(e lasciandolo così cancellerei informazioni)
Quindi così
Codice:
...else if(v[dim-1]!='b') return false;
nick_10
Junior Member
Junior Member
 
Messaggio: 371 di 373
Iscritto il: 17/11/2016, 17:21

Re: Esercizio grammatiche e ricorsione

Messaggioda apatriarca » 16/12/2018, 01:02

Non ho controllato tutto, ma nel primo esercizio A può essere vuoto..
apatriarca
Moderatore
Moderatore
 
Messaggio: 5174 di 5214
Iscritto il: 08/12/2008, 21:37
Località: Londra


Torna a Informatica

Chi c’è in linea

Visitano il forum: Nessuno e 3 ospiti