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 $. |
|
|
|
