Grammatica libera da contesto e implementazione funzione ricorsiva C
Ciao a tutti! Sto studiando linguaggi e grammatiche libere dal contesto e sono un po' in difficoltà con questo esercizio
"a)Si fornisca una grammatica libera G che generi il linguaggio $L={0^n1^m0^n|n>0,m>0}$
b)Fornire l’albero sintattico della stringa $w = 0011100$
c)Dimostrare che L è libero ma non è regolare.
d)Scrivere in C una o più funzioni ricorsive che dato un array a di interi e la sua dimensione dim, controllino se
la sequenza di interi contenuta nell’array è una sequenza che appartiene al linguaggio L"
Allora per il punto a) avevo pensato alle seguenti produzioni: $S->ABA; A->0|0A; B->1|1B$. Non sono sicuro però della correttezza; un motivo è che mi incasino con l'albero del punto successivo e forse questo mi fa pensare che non c'è qualcosa di sbagliato.
Il punto c) invece per dimostrare che è libero avrei bisogno della correttezza della grammatica(
), mentre ho dimostrato che non è regolare con il Pumping Lemma
Per quanto riguarda la funzione ricorsiva davvero non saprei nemmeno come partire...quali potrebbero essere i miei casi base ad esempio
"a)Si fornisca una grammatica libera G che generi il linguaggio $L={0^n1^m0^n|n>0,m>0}$
b)Fornire l’albero sintattico della stringa $w = 0011100$
c)Dimostrare che L è libero ma non è regolare.
d)Scrivere in C una o più funzioni ricorsive che dato un array a di interi e la sua dimensione dim, controllino se
la sequenza di interi contenuta nell’array è una sequenza che appartiene al linguaggio L"
Allora per il punto a) avevo pensato alle seguenti produzioni: $S->ABA; A->0|0A; B->1|1B$. Non sono sicuro però della correttezza; un motivo è che mi incasino con l'albero del punto successivo e forse questo mi fa pensare che non c'è qualcosa di sbagliato.
Il punto c) invece per dimostrare che è libero avrei bisogno della correttezza della grammatica(
), mentre ho dimostrato che non è regolare con il Pumping LemmaPer quanto riguarda la funzione ricorsiva davvero non saprei nemmeno come partire...quali potrebbero essere i miei casi base ad esempio
Risposte
Penso che quello che ho scritto prima non abbia alcun senso...ragionandoci ho tirato fuori queste produzioni che spero ora funzionino: $S->0S0|A; A->1A|1$
Ho fatto anche l'albero sintattico specifico per quella stringa w.
Ora devo provare a scrivere la funzione ricorsiva.
Per farlo come potrei iniziare? Intanto immagino io debba assumere che ci possano essere solo 0 e 1 come simboli(altrimenti con tutti gli altri numeri
)
Per fare un passo base devo utilizzare la dimensione dell'array? Cioè ad esempio sfruttare il fatto che la stringa più corta possibile che L accetta è 010?
Ho fatto anche l'albero sintattico specifico per quella stringa w.
Ora devo provare a scrivere la funzione ricorsiva.
Per farlo come potrei iniziare? Intanto immagino io debba assumere che ci possano essere solo 0 e 1 come simboli(altrimenti con tutti gli altri numeri
)Per fare un passo base devo utilizzare la dimensione dell'array? Cioè ad esempio sfruttare il fatto che la stringa più corta possibile che L accetta è 010?
Se i valori sono diversi da zero e uno allora la funzione ricorsiva dovrà restituire falso.
L'idea è qualcosa come il seguente:
dove testAllOnes controlla che ci siano solo degli uno nella sequenza.
L'idea è qualcosa come il seguente:
bool testSequence(int n, int array[static n])
{
if (n <= 0) { return true; }
else if (array[0] != array[n-1]) {
// Nota che eliminiamo uno zero ogni volta da entrambi i lati e poi ci sono solo degli uno..
return false;
} else if (array[0] == 0) {
return testSequence(n-2, array+1);
} else if (array[0] == 1) {
return testAllOnes(n-2, array+1);
} else {
return false;
}
}
dove testAllOnes controlla che ci siano solo degli uno nella sequenza.
Intanto grazie per la risposta.
Mi è sorto un dubbio(di nuovo) sulle produzioni della grammatica. Così scritte, potrei generare anche stringhe in cui lo 0 non appare mai, ma queste nel linguaggio non ci sono
Dunque io le modificherei così: $S->0S0|0A0; A->1A|1$
Mi è sorto un dubbio(di nuovo) sulle produzioni della grammatica. Così scritte, potrei generare anche stringhe in cui lo 0 non appare mai, ma queste nel linguaggio non ci sono
Dunque io le modificherei così: $S->0S0|0A0; A->1A|1$
Non avevo notato che le stringhe vuote non erano accettabili. In tal caso devi modificare anche la funzione ricorsiva che ti ho scritto in modo da non accettare la stringa vuota. Credo tu abbia necessariamente bisogno di un'altra funzione.
Se iniziassi così ad esempio:
poi potrei fare un caso base che ritorni true o false con dim=3;
poi aggiungerei i tre else if che hai abbozzato tu
Potrebbe andare?
bool check(int v[],int dim){
if(dim<=2) return false; //tanto la minima stringa possibile ha lunghezza 3poi potrei fare un caso base che ritorni true o false con dim=3;
poi aggiungerei i tre else if che hai abbozzato tu
Potrebbe andare?
No perché chiamando la funzione ricorsivamente si arriverà necessariamente ad avere 3 elementi o meno.
E non è quello lo scopo della ricorsione?
Ma se restituisci false appena arrivi a quel caso allora non ci saranno mai casi in cui la funzione restituirà true..
Una cosa del genere? Manca la parte sul checkone ancora
bool check(int v[],int dim,int from){
if(dim<=2) return false;
if(from>=dim) return true;
else if(dim==3){
if((v[0]==0) && (v[1]==1) && (v[2]==0)) return true;
else return false;
}
else if((v[from]!=v[dim-1])&&(v[0]!=0)) return false;
else if(v[from]==0) {
return check(v+1,dim-2,from+1);
}
else if(v[from]==1) return checkone(v+1,dim-2);
else return false;
}
Come ultima cosa ho scritto questo
Però ci sono dei problemi...ad esempio legge anche stringhe con tutti 1 oppure non legge stringhe del tipo 0110
Per stasera la chiudo qui che non ragiono più. Riproverò sicuramente domani
bool checkone(int v[],int dim){
if(dim<=0) return false;
else if(dim==1){
if(v[0]==1) return true;
else return false;
}
else return checkone(v+1,dim-1);
}
bool check(int v[],int dim,int from){
if(dim<=2) return false;
if(from>=dim) return true;
else if(dim==3){
if((v[0]==0) && (v[1]==1) && (v[2]==0)) return true;
else return false;
}
else if((v[from]!=v[dim-1])&&(v[0]!=0)) return false;
else if(v[from]==0) {
return check(v+1,dim-2,from+1);
}
else if(v[from]==1) return checkone(v+1,dim-2);
else return false;
}Però ci sono dei problemi...ad esempio legge anche stringhe con tutti 1 oppure non legge stringhe del tipo 0110
Per stasera la chiudo qui che non ragiono più. Riproverò sicuramente domani
Qual'è il significato di [tt]from[/tt]?
Un modo per implementare le funzione ricorsive per una qualche grammatica consiste nell'avere una funzione per ogni simbolo non terminale. Dalle produzione che hai scritto è chiaro che qualsiasi stringa prodotta da \(S\) deve essere compresa tra zeri. Puoi quindi iniziare a scriverla come condizione iniziale:
A questo punto devi stabilire quale delle due regole usare per continuare con il test. Il modo più semplice seguendo le regole di produzione è quella di provare entrambe le strade come segue:
Tuttavia una delle due strade verrà subito esclusa e converrebbe quindi verificare la condizione immediatamente. Un modo sarebbe quello di modificare la grammatica in questo modo:
\[ \begin{align*} S &\to 0\,S\,0\;\mid\;0\,1\,A\,0 \\ A &\to \epsilon\;\mid\;1\,A \end{align*} \]
dove \(\epsilon\) indica la stringa vuota. A questo punto le due produzioni sono facilmente distinguibili senza dover andare a "tentativi". Ti lascio il compito di implementare questa ultima idea..
Un modo per implementare le funzione ricorsive per una qualche grammatica consiste nell'avere una funzione per ogni simbolo non terminale. Dalle produzione che hai scritto è chiaro che qualsiasi stringa prodotta da \(S\) deve essere compresa tra zeri. Puoi quindi iniziare a scriverla come condizione iniziale:
bool checkS(int v[], int n)
{
if (n < 2 || (v[0] != 0 && v[1] != 0)) { return false; }
// resto della funzione
}
A questo punto devi stabilire quale delle due regole usare per continuare con il test. Il modo più semplice seguendo le regole di produzione è quella di provare entrambe le strade come segue:
bool checkS(int v[], int n)
{
if (n < 2 || (v[0] != 0 && v[1] != 0)) { return false; }
return checkS(v+1, n-2) || checkA(v+1, n-2);
}
Tuttavia una delle due strade verrà subito esclusa e converrebbe quindi verificare la condizione immediatamente. Un modo sarebbe quello di modificare la grammatica in questo modo:
\[ \begin{align*} S &\to 0\,S\,0\;\mid\;0\,1\,A\,0 \\ A &\to \epsilon\;\mid\;1\,A \end{align*} \]
dove \(\epsilon\) indica la stringa vuota. A questo punto le due produzioni sono facilmente distinguibili senza dover andare a "tentativi". Ti lascio il compito di implementare questa ultima idea..
Scusa la versione di prima era molto incasinata...con quel from volevo verificare se il primo elemento di ogni pezzo di array (ad ogni passo della ricorsione) fosse 0 o 1 e così dividere i due casi
Comunque ho provato a seguire i tuoi consigli seguendo le produzioni della grammatica(in particolare quelle modificate con l'epsilon) e ho scritto questo:
Comunque ho provato a seguire i tuoi consigli seguendo le produzioni della grammatica(in particolare quelle modificate con l'epsilon) e ho scritto questo:
bool checkA(int v[],int dim){
if(dim==0) return true;
if(v[0]!=1) return false;
else return checkA(v+1,dim-1);
}
bool checkS(int v[],int dim){
if((dim<2)||(v[0]!=0)||(v[0]!=v[dim-1])) return false;
else if(v[1]==0) return checkS(v+1,dim-2);
else if(v[1]==1) return checkA(v+1,dim-2);
else return false;
}
Devi cambiare anche il test sulla dimensione. Hai bisogno di almeno 3 valori a questo punto.
Mmm...dov'è che può andare male il mio frammento di codice?
Hai ragione, dovrebbe funzionare lo stesso.
Grazie mille per l'aiuto!! 
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo