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

.dsy:it.
//www.dsy.it

Esercizio su CFG (Context Free Grammar)

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

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