Mer 21 Agosto, 08:58:15 - 2019

Autore Topic: Homework3  (Letto 8227 volte)

0 Utenti e 1 Visitatore stanno visualizzando questo topic.

Offline spin

  • Ricercatore
  • ****
  • Post: 274
  • FeedBack: +3/-6
    • Mostra profilo
Re: Homework3
« Risposta #15 il: Sab 11 Dicembre, 23:18:07 - 2010 »
scusi prof..
per il metodo verifica, dobbiamo praticamente verificare che la lista di produzioni che gli passiamo faccia parte della grammatica, che quella lista(si presume ordinata) debba creare la stringa di input e che la prima produzione parta da dall'assioma della grammatica.
giusto?
ho dimenticato qualcosa?

EDIT:

passandogli una lista del tipo: { S->aB    A->c   B->bA  }
e stringa di input: "abc"

dobbiamo dire subito a priori che è false la verifica, perchè la lista non è ordinata?


le produzioni nn devono essere necessariamente in ordine (nn c'è scritto da nessuna parte nella teoria dei modelli che le produzioni vadano scritte in qualche ordine preciso).
Perciò credo che il metodo deve restitituire true in questo caso.


correzione: pensavo vi riferiste al metodo riconosceInput (dove l'ordine con cui sono salvate le produzioni nn conta). Nel caso del metodo verificaDerivazione l'ordine conta perchè si tratta dia una derivazione quindi di un ordine preciso di produzioni. Chiedo scusa per la svista^^
« Ultima modifica: Dom 12 Dicembre, 02:19:21 - 2010 da spin »

Offline gabry

  • Studente di Dottorato
  • ***
  • Post: 141
  • FeedBack: +21/-17
    • Mostra profilo
Re: Homework3
« Risposta #16 il: Sab 11 Dicembre, 23:29:33 - 2010 »
Citazione
Inserisci citazione
scusi prof..
per il metodo verifica, dobbiamo praticamente verificare che la lista di produzioni che gli passiamo faccia parte della grammatica, che quella lista(si presume ordinata) debba creare la stringa di input e che la prima produzione parta da dall'assioma della grammatica.
giusto?
ho dimenticato qualcosa?

EDIT:

passandogli una lista del tipo: { S->aB    A->c   B->bA  }
e stringa di input: "abc"

dobbiamo dire subito a priori che è false la verifica, perchè la lista non è ordinata?

no, deve restituire false. legger pr credere:

Citazione
 boolean verificaDerivazione(
Grammatica g, List<Produzione> p, String s)
 Verica se la sequenza di produzioni p rappresenta una derivazione
per la stringa s (applicando le produzioni nell'ordine in cui
sono riportate nella sequenza).
"cerco un centro di gravita` permanente..."
informatico per caso
_

Offline gabry

  • Studente di Dottorato
  • ***
  • Post: 141
  • FeedBack: +21/-17
    • Mostra profilo
Re: Homework3
« Risposta #17 il: Sab 11 Dicembre, 23:37:19 - 2010 »
scusate un attimo, vorrei cmq riallacciarmi alla domanda di lelinolino: il metodo verifcaDerivazione prende come parametro una grammatica, una lista di produzioni e una stringa.... ma se l'obiettivo e` verificare che la sequenza di produzioni generi la stringa, la grammatica non serve a nulla! quindi dobbiamo verificare anche che le produzioni appartengano alla grammatica? o forse solo che il primo non terminale di sinistra sia l'assioma di quella grammatica?
« Ultima modifica: Sab 11 Dicembre, 23:43:37 - 2010 da gabry »
"cerco un centro di gravita` permanente..."
informatico per caso
_

Offline Wes90

  • Studente di Dottorato
  • ***
  • Post: 200
  • FeedBack: +17/-46
    • Mostra profilo
Re: Homework3
« Risposta #18 il: Dom 12 Dicembre, 00:55:34 - 2010 »
in che senso non sarebbe una sequenza di produzioni valida??

Nel senso che la seconda produzione non viene utilizzata e la terza non è del tipo S->a ma contiene un non terminale a destra quindi non "chiude" la stringa,
quindi nessuna stringa può essere prodotta da quella sequenza.

Offline vinkia

  • Guru
  • Professore Associato
  • *****
  • Post: 696
  • FeedBack: +70/-30
  • http://teamend.altervista.org/chi-siamo
    • Mostra profilo
    • TeamEnd applicazioni per Android e non solo...
Re: Homework3
« Risposta #19 il: Dom 12 Dicembre, 03:38:46 - 2010 »
scusate un attimo, vorrei cmq riallacciarmi alla domanda di lelinolino: il metodo verifcaDerivazione prende come parametro una grammatica, una lista di produzioni e una stringa.... ma se l'obiettivo e` verificare che la sequenza di produzioni generi la stringa, la grammatica non serve a nulla! quindi dobbiamo verificare anche che le produzioni appartengano alla grammatica? o forse solo che il primo non terminale di sinistra sia l'assioma di quella grammatica?

Io credo che devi verificare solamente che il primo elemento della lista sia un assioma. Io ho sfruttato la grammatica con il metodo getAssioma()
Non preoccuparti solo di essere migliore dei tuoi contemporanei o dei tuoi predecessori. Cerca solo di essere migliore di te stesso.

http://teamend.altervista.org/chi-siamo

Offline johnny-Mnem

  • Neo-Laureato
  • **
  • Post: 56
  • FeedBack: +3/-7
    • Mostra profilo
Re: Homework3
« Risposta #20 il: Dom 12 Dicembre, 04:11:04 - 2010 »
mmm...

Offline patoz

  • Studente di Dottorato
  • ***
  • Post: 174
  • FeedBack: +45/-49
    • Mostra profilo
Re: Homework3
« Risposta #21 il: Dom 12 Dicembre, 07:17:34 - 2010 »
Professore, nel testo dell'homework c'è scritto:
Citazione
La verifica dei contributi inviati verra' fatta utilizzando input di test validi. Lo studente quindi non dovra' preoccuparsi controllare la correttezza dell'input fornito. Le grammatiche utilizzate per il test sono corrette e contengono l'assioma e l'alfabeto. Le produzioni fanno riferimento a simboli terminali appartenenti all'alfabeto fornito. La grammatica puo' non avere nessuna produzione. La grammatica fornita non contiene ε − produzioni

Allora, possiamo supporre che non abbiamo ad esempio, nella stessa grammatica, la ripetizione di una stessa produzione? Ad esempio:

Grammatica g = new Grammatica("S", new char[]{'a', 'b'});
      g.addProduzione(new Produzione("S", 'a', "S"));
                g.addProduzione(new Produzione("S", 'a', "S"));
      g.addProduzione(new Produzione("S", 'b'));


Questa non può essere una grammatica che viene passata come input o si?
Inoltre, ci possono essere produzioni "superflue", cioè del tipo:


Grammatica g = new Grammatica("S", new char[]{'a', 'b'});
      g.addProduzione(new Produzione("S", 'a', "S"));
                g.addProduzione(new Produzione("S", 'a', "B"));
                g.addProduzione(new Produzione("B", 'b'));
      g.addProduzione(new Produzione("S", 'b'));


?

Infine, nella descrizione del metodo verificaDerivazione c'è scritto:

Citazione
Verifica se la sequenza di produzioni p rappresenta una derivazione per la stringa s.

Per verificarlo, non ci serve la grammatica. O dobbiamo pure fare i controlli che le produzioni appartengano alla grammatica e che il primo elemento della lista abbia come non terminale a sinistra l'assioma?

Infine, nel caso gli si passi una grammatica vuota, il metodo riconosceInput deve restituire null a qualsiasi stringa, anche quella vuota, poiché non sono ammesse ε − produzioni, giusto? Grazie mille :D
"Tira more a potato's hair than buoi carret in Arcore's nights"

Offline vermillion89

  • Professore Associato
  • *
  • Post: 531
  • FeedBack: +25/-15
    • Mostra profilo
Re: Homework3
« Risposta #22 il: Dom 12 Dicembre, 13:32:36 - 2010 »
come faccio a capire se una stringa appartiene al linguaggio generato da una grammatica g ? Non voglio sapere il codice del programma ma teoricamente come si fa? Mi basta anche un esempio per capire come fare  ;D Vi ringrazio in anticipo per l'aiuto
« Ultima modifica: Dom 12 Dicembre, 13:51:13 - 2010 da vermillion89 »

Offline devilman

  • Studente di Dottorato
  • ***
  • Post: 171
  • FeedBack: +6/-8
    • Mostra profilo
Re: Homework3
« Risposta #23 il: Dom 12 Dicembre, 13:42:07 - 2010 »
buongiorno a tutti!

prof. Millozzi ho una domanda da farle. Nella descrizione del metodo

Codice: [Seleziona]
public List<Produzione> riconosceInput(Grammatica g, String input)
c'è scritto "Controlla se la stringa input appartiene al linguaggio generato dalla grammatica g. In caso positivo restituisce la sequenza di produzioni applicate (dall'assioma alla produzione terminale), mentre se la stringa non e' riconosciuta dalla grammatica ritorna null." Quello che mi chiedo, e che le chiedo, è se dobbiamo inserire anche l'assioma nella lista delle produzioni, perché in caso affermativo come faccio a inserire l'assioma nella lista, visto che l'assioma è una stringa e che la lista delle produzioni può contenere, appunto, solo oggetti di tipo "Produzione"?

spero di essere stato chiaro. in attesa di una sua risposta, le mando cordiali saluti.

Federico
Io sono il demone nato per eliminare voi tutti dalla faccia della Terra. Io sono DEVILMAN!

Offline emanuelino

  • Professore Associato
  • *
  • Post: 595
  • FeedBack: +64/-29
    • Mostra profilo
Re: Homework3
« Risposta #24 il: Dom 12 Dicembre, 14:10:16 - 2010 »
gabry io penso che la grammatica sia necessaria... una stringa potrebbe essere generata da una lista di produzioni che però potrebbero non appartenere a quella grammatica, e quindi in quel caso restituire false

Offline spin

  • Ricercatore
  • ****
  • Post: 274
  • FeedBack: +3/-6
    • Mostra profilo
Re: Homework3
« Risposta #25 il: Dom 12 Dicembre, 14:22:45 - 2010 »
gabry io penso che la grammatica sia necessaria... una stringa potrebbe essere generata da una lista di produzioni che però potrebbero non appartenere a quella grammatica, e quindi in quel caso restituire false

Quindi prima di eseguire il metodo vero e proprio dobbiamo controllare che tutte le produzioni della lista appartengono alla grammatica giusto?

Offline emanuelino

  • Professore Associato
  • *
  • Post: 595
  • FeedBack: +64/-29
    • Mostra profilo
Re: Homework3
« Risposta #26 il: Dom 12 Dicembre, 14:45:20 - 2010 »
ragazzi scusate mi sta nascendo un dubbio atroce. L'homework praticamente richiede che vengano generati tutti i passi necessari per generare l'input oppure le produzioni non ripetute che sono capaci di generarlo? mi spiego bene con un esempio. se io ho la stringa aaaab e una grammatica definita come S->aS S->b il risultato deve essere S->aS,S->aS,S->aS,S->aS,S->b oppure semplicemente S->aS,S->b?? ovviamente questo si riferisce anche al caso di verifica cioè passandogli una stringa aaaab deve restituire true se gli passo una lista contenente le produzioni  S->aS,S->aS,S->aS,S->aS,S->b oppure solo con S->aS,S->b??

Offline spin

  • Ricercatore
  • ****
  • Post: 274
  • FeedBack: +3/-6
    • Mostra profilo
Re: Homework3
« Risposta #27 il: Dom 12 Dicembre, 14:49:09 - 2010 »
ragazzi scusate mi sta nascendo un dubbio atroce. L'homework praticamente richiede che vengano generati tutti i passi necessari per generare l'input oppure le produzioni non ripetute che sono capaci di generarlo? mi spiego bene con un esempio. se io ho la stringa aaaab e una grammatica definita come S->aS S->b il risultato deve essere S->aS,S->aS,S->aS,S->aS,S->b oppure semplicemente S->aS,S->b?? ovviamente questo si riferisce anche al caso di verifica cioè passandogli una stringa aaaab deve restituire true se gli passo una lista contenente le produzioni  S->aS,S->aS,S->aS,S->aS,S->b oppure solo con S->aS,S->b??

credo che debba generare una lista con l'intera sequenza delle produzioni usate per generare la stringa.

Nel caso di aab e produzioni S->aS, S->b, dovrebbe generare una lista con questa sequenza:

[ S->aS, S->aS, S->b ].

Peccato che nn abbiano messo un esempio sul pdf cosi sarebbe stato piu chiaro, cmq credo proprio che sia cosi^^

Offline lelinolino

  • Guru
  • Professore Ordinario
  • *****
  • Post: 766
  • FeedBack: +81/-28
    • Mostra profilo
    • LeleWorlds
Re: Homework3
« Risposta #28 il: Dom 12 Dicembre, 15:12:01 - 2010 »
Citazione
Peccato che nn abbiano messo un esempio sul pdf cosi sarebbe stato piu chiaro, cmq credo proprio che sia cosi^^

quoto!

Offline vinkia

  • Guru
  • Professore Associato
  • *****
  • Post: 696
  • FeedBack: +70/-30
  • http://teamend.altervista.org/chi-siamo
    • Mostra profilo
    • TeamEnd applicazioni per Android e non solo...
Re: Homework3
« Risposta #29 il: Dom 12 Dicembre, 15:36:21 - 2010 »
secondo voi come è possibile che il metodo java

g.getProduzioni().containsAll(produzioni)

restituisca false, anche se tutti gli elementi di (produzioni) sono contenuti in(g.getProduzioni)????

Sto diventando matto ho messo delle stampe delle due liste e sono ok!!!ma il risultato di containsAll è errato!!!

Cerco di farvi capire meglio, la riga:

System.out.println("Io devo essere true, poichè "+g.getProduzioni()+" contiene tutti"+produzioni+"pero io sono:"+g.getProduzioni().containsAll(produzioni));

stampa le due liste, ma poi mi dice false, anche se la grammatica contiene gli elementi della lista di produzione!

Non preoccuparti solo di essere migliore dei tuoi contemporanei o dei tuoi predecessori. Cerca solo di essere migliore di te stesso.

http://teamend.altervista.org/chi-siamo