Grammatica libera da contesto e implementazione funzione ricorsiva C
Inviato: 11/12/2018, 18:34
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 Lemma
Per quanto riguarda la funzione ricorsiva davvero non saprei nemmeno come partire...quali potrebbero essere i miei casi base ad esempio