.dsy:it. - Esercizio su CFG (Context Free Grammar)

.dsy:it. (http://www.dsy.it/forum/)
- Linguaggi formali e automi (http://www.dsy.it/forum/forumdisplay.php?forumid=132)
-- Esercizio su CFG (Context Free Grammar) (http://www.dsy.it/forum/showthread.php?threadid=32715)

Posted by Bemipefe on 10-11-2007 18:49:

Esercizio su CFG (Context Free Grammar)

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

__________________
_/\/\/\Bemipefe/\/\/\_

Posted by Polsy on 10-11-2007 20:26:

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.

Posted by Bemipefe on 11-11-2007 11:50:

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

__________________
_/\/\/\Bemipefe/\/\/\_

All times are GMT. The time now is 08:20.

Show all 3 posts from this thread on one page