Bemipefe

.fedelissimo.

User info:

Registered: Jul 2005
Posts: 44 (0.01 al dì)
Location: P.M.
Corso: Scienze Informatiche
Anno: Secondo (...teoricamente)
Time Online: 2:59:00: [...]
Status: Offline

Post actions:

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.

code:

S ->(SB | $              /*$ = parola vuota*/
B -> )

code:

S -> $ | (S)S

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

Polsy

.arcimaestro.

User info:

Registered: Dec 2003
Posts: 477 (0.06 al dì)
Location:
Corso: Info phd
Anno:
Time Online: 17 Days, 17:11:50 [...]
Status: Offline

Post actions:

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

.fedelissimo.

User info:

Registered: Jul 2005
Posts: 44 (0.01 al dì)
Location: P.M.
Corso: Scienze Informatiche
Anno: Secondo (...teoricamente)
Time Online: 2:59:00: [...]
Status: Offline

Post actions:

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/\/\/\_