Grammatica libera da contesto e implementazione funzione ricorsiva C

Messaggioda nick_10 » 11/12/2018, 19: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( :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
nick_10
Junior Member
Junior Member
 
Messaggio: 347 di 377
Iscritto il: 17/11/2016, 17:21

Re: Grammatica libera da contesto e implementazione funzione ricorsiva C

Messaggioda nick_10 » 12/12/2018, 17:37

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?
nick_10
Junior Member
Junior Member
 
Messaggio: 351 di 377
Iscritto il: 17/11/2016, 17:21

Re: Grammatica libera da contesto e implementazione funzione ricorsiva C

Messaggioda apatriarca » 12/12/2018, 22:27

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.
apatriarca
Moderatore
Moderatore
 
Messaggio: 5167 di 5300
Iscritto il: 08/12/2008, 21:37
Località: Londra

Re: Grammatica libera da contesto e implementazione funzione ricorsiva C

Messaggioda nick_10 » 12/12/2018, 23:18

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$
nick_10
Junior Member
Junior Member
 
Messaggio: 354 di 377
Iscritto il: 17/11/2016, 17:21

Re: Grammatica libera da contesto e implementazione funzione ricorsiva C

Messaggioda apatriarca » 13/12/2018, 02:15

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.
apatriarca
Moderatore
Moderatore
 
Messaggio: 5168 di 5300
Iscritto il: 08/12/2008, 21:37
Località: Londra

Re: Grammatica libera da contesto e implementazione funzione ricorsiva C

Messaggioda nick_10 » 14/12/2018, 00:02

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?
nick_10
Junior Member
Junior Member
 
Messaggio: 358 di 377
Iscritto il: 17/11/2016, 17:21

Re: Grammatica libera da contesto e implementazione funzione ricorsiva C

Messaggioda apatriarca » 14/12/2018, 00:05

No perché chiamando la funzione ricorsivamente si arriverà necessariamente ad avere 3 elementi o meno.
apatriarca
Moderatore
Moderatore
 
Messaggio: 5169 di 5300
Iscritto il: 08/12/2008, 21:37
Località: Londra

Re: Grammatica libera da contesto e implementazione funzione ricorsiva C

Messaggioda nick_10 » 14/12/2018, 00:09

E non è quello lo scopo della ricorsione? :roll:
nick_10
Junior Member
Junior Member
 
Messaggio: 359 di 377
Iscritto il: 17/11/2016, 17:21

Re: Grammatica libera da contesto e implementazione funzione ricorsiva C

Messaggioda apatriarca » 14/12/2018, 00:28

Ma se restituisci false appena arrivi a quel caso allora non ci saranno mai casi in cui la funzione restituirà true..
apatriarca
Moderatore
Moderatore
 
Messaggio: 5170 di 5300
Iscritto il: 08/12/2008, 21:37
Località: Londra

Re: Grammatica libera da contesto e implementazione funzione ricorsiva C

Messaggioda nick_10 » 14/12/2018, 00:28

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;
}
nick_10
Junior Member
Junior Member
 
Messaggio: 360 di 377
Iscritto il: 17/11/2016, 17:21

Prossimo

Torna a Informatica

Chi c’è in linea

Visitano il forum: Nessuno e 7 ospiti