 | |
Il progetto dsy.it è l'unofficial support site dei corsi di laurea del Dipartimento di Scienze dell'Informazione e del Dipartimento di Informatica e Comunicazione della Statale di Milano. E' un servizio degli studenti per gli studenti, curato in modo no-profit da un gruppo di essi. I nostri servizi comprendono aree di discussione per ogni Corso di Laurea, un'area download per lo scambio file, una raccolta di link e un motore di ricerca, il supporto agli studenti lavoratori, il forum hosting per Professori e studenti, i blog, e molto altro...
In questa sezione è indicizzato in textonly il contenuto del nostro forum |
Esercizio su CFG (Context Free Grammar)
Clicca QUI per vedere il messaggio nel forum |
| Bemipefe |
Salve!
Sto studiando le CFG (context free grammar) spero di essere nella sezione giusta.
Allora ... riferendomi all'esercizio seguente:
code:
- Costruire una CFG che generi l’insieme di tutte le stringhe di parentesi correttamente annidate.
Per generare tale linguaggio a me era venuto in mente la banale:
code:
S ->(SB | $ /*$ = parola vuota*/
B -> )
Pero come soluzione viene data:
code:
S -> $ | (S)S
Ora tutte e due generano un linguaggio di parentesi correttamente annidate. Nessuna delle due però riesce a generare ad esempio questa stringa : "(()())"
Quindi non ho capito se si richiede un linguaggio che contenga parentesi correttamente annidate o il linguaggio di TUTTE le stringhe fatte da parentesi correttamente annidate.
Grazie!
Buon Lavoro |
| Polsy |
Veniva richiesta una grammatica che generasse TUTTE le stringhe di parentesi ben annidate, la seconda grammatica è giusta, infatti genera anche (()()):
S => (S)S => (S) => ((S)S) => (()S) => (()(S)S) => (()()S) => (()())
Il problema della prima grammatica è che non ti permette di affiancare parentesi, ma solo di annidarle, infatti visto che B può generare solo ")", è analoga a
S -> (S) | $
aggiungendo una S in fondo invece hai la possibilità di generare un'altra coppia di parentesi dopo quella chiusa. |
| Bemipefe |
Grazie!
Tutto chiaro....ma mi rende perplesso il fatto che quando si applica la regola S -> $ la si possa applicare solo per alcune variabili. Io pensavo che applicando quella regola, tutte le variabili venissere automaticamente sostituite da $. |
|
|
|
|
