Pages: [1]   Go Down
Print
Author Topic: dubbio esercizio compito del 21/09/2009  (Read 1016 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
esteta84
Apprendista Forumista
**
Offline Offline

Posts: 284



« on: 22-09-2009, 08:08:08 »

Ciao ragazzi,
nel compito di ieri c'era un esercizio (mi pare che fosse il numero 9) in cui veniva data una grammatica con le relative produzioni e si richiedeva di costruire le derivazioni per una determinata stringa ad esempio x=abcbba.
Inoltre si richiedeva di verificare se la stringa x appartenesse a L(G) e infine bisognava verificare se la grammatica data era una grammatica context-free.

Qualcuno si ricorda perfettamente il testo?
Se si, come lo avete risolto?

Grazie nuovamente
Logged
Alexios
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 128



« Reply #1 on: 22-09-2009, 14:35:14 »

Esercizio 9

Sia G=({S,A},{a,b,c},P,S) dove P contiene le seguenti regole
S->SA|a, A->bAc|bc
Scrivere una derivazione della stringa abcbbcc ∈ L(G) e costruire l'albero di derivazione corrispondente.

La grammatica precedente è una grammatica context-free? Giustificare la risposta
Logged
Rebel
Matricola
*
Offline Offline

Gender: Male
Posts: 75



« Reply #2 on: 22-09-2009, 15:39:05 »

Io l'ho risolto così:
S => SA => SAA => SAbAC => SAbbcc => Sbcbbcc => abcbbcc
Una grammatica è detta context free se ogni produzione in P ha la forma
A -> α con A€N e α€(N U Σ)*.
Pertanto la grammatica in questione "dovrebbe" essere context free. O sbaglio?

Secondo voi è giusto?

Ciao
Logged

L'evoluzione è storia dimenticata a memoria.
Psycho
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 497



« Reply #3 on: 05-10-2009, 17:16:51 »

Io l'ho risolto così:
S => SA => SAA => SAbAC => SAbbcc => Sbcbbcc => abcbbcc
Una grammatica è detta context free se ogni produzione in P ha la forma
A -> α con A€N e α€(N U Σ)*.
Pertanto la grammatica in questione "dovrebbe" essere context free. O sbaglio?

Secondo voi è giusto?

Ciao

io l'ho risolto esattamente in questo modo..speriamo bene  yoh
Logged

Segnate le date, cancellate gli altri impegni, chiudete i libri e i quaderni e per un attimo accorgetevi che la vita non è piatta ma può essere... 3d!
Pages: [1]   Go Up
Print
Jump to: