Pagina 1 di 2

Grammatica libera da contesto e implementazione funzione ricorsiva C

MessaggioInviato: 11/12/2018, 18:34
da nick_10
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( :roll: ), 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

Re: Grammatica libera da contesto e implementazione funzione ricorsiva C

MessaggioInviato: 12/12/2018, 16:37
da nick_10
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 :shock: :shock: )
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?

Re: Grammatica libera da contesto e implementazione funzione ricorsiva C

MessaggioInviato: 12/12/2018, 21:27
da apatriarca
Se i valori sono diversi da zero e uno allora la funzione ricorsiva dovrà restituire falso.

L'idea è qualcosa come il seguente:
Codice:
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.

Re: Grammatica libera da contesto e implementazione funzione ricorsiva C

MessaggioInviato: 12/12/2018, 22:18
da nick_10
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$

Re: Grammatica libera da contesto e implementazione funzione ricorsiva C

MessaggioInviato: 13/12/2018, 01:15
da apatriarca
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.

Re: Grammatica libera da contesto e implementazione funzione ricorsiva C

MessaggioInviato: 13/12/2018, 23:02
da nick_10
Se iniziassi così ad esempio:
Codice:
bool check(int v[],int dim){
    if(dim<=2) return false; //tanto la minima stringa possibile ha lunghezza 3

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?

Re: Grammatica libera da contesto e implementazione funzione ricorsiva C

MessaggioInviato: 13/12/2018, 23:05
da apatriarca
No perché chiamando la funzione ricorsivamente si arriverà necessariamente ad avere 3 elementi o meno.

Re: Grammatica libera da contesto e implementazione funzione ricorsiva C

MessaggioInviato: 13/12/2018, 23:09
da nick_10
E non è quello lo scopo della ricorsione? :roll:

Re: Grammatica libera da contesto e implementazione funzione ricorsiva C

MessaggioInviato: 13/12/2018, 23:28
da apatriarca
Ma se restituisci false appena arrivi a quel caso allora non ci saranno mai casi in cui la funzione restituirà true..

Re: Grammatica libera da contesto e implementazione funzione ricorsiva C

MessaggioInviato: 13/12/2018, 23:28
da nick_10
Una cosa del genere? Manca la parte sul checkone ancora
Codice:
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;
}