| Autore |
 Discussione  |
|
|
ekkekkazz
Utente innocuo
|
 Inserito il - 24/04/2006 : 14:01:13
|
come l'avete risolto? io ci sono riuscito solo in treno, quando me ne tornavo... mi sono trovato una grammatica CS cioè
S->R|aba, R->(a)R(BA)|a(BA), AB->BA, AA->Aa, BB->Bb, aBb->abb, bAa->baa...
quindi, avrei dovuto dimostrare che la correttezza...
e quindi L è CS.
che dite?
|
|
|
ianus
Nuovo Utente
|
Inserito il - 24/04/2006 : 14:30:01
|
se il linguaggio è
a^n b^n a^n
una possibile soluzione poteva essere la seguente
S-> aSBA | aBA
AB -> BA
aB -> ab
bB -> bb
bA -> aa
rifacendoti al caso a^n b^n c^n del semeraro |
 |
|
|
ekkekkazz
Utente innocuo
|
Inserito il - 24/04/2006 : 17:02:45
|
Citazione:
Messaggio inserito da ianus
S-> aSBA | aBA
AB -> BA
aB -> ab
bB -> bb
bA -> aa
S=>aSBA=>aaBABA=>aabABA=>aabBAA=>aabbAA=>aabaaA oppure
S=>aSBA=>aaBABA=>aabABA=>aaaaBA oppure
S=>aSBA=>aaBABA=>aaBBAA=>aabBAA=>aabbAA=>aabaaA che non sono in L.
sicuro di aver ricopiato bene le produzioni?
cmq si è quella la grammatica... simile
ma L è CS giusto? |
|
|
|
ianus
Nuovo Utente
|
Inserito il - 24/04/2006 : 17:43:39
|
no non sono sicuro ;) cmq na roba del genere, ovviamente è una CS. Non potrebbe mai essere CF.
comunque sia mi sembra di vedere una cosa dalle produzioni che hai ricavato
S=>aSBA=>aaBABA=>aabABA=>aabBAA=>aabbAA=>aabaaA
qui al secondo passo dovevi applicare la produzione AB->BA e poi le altre produzioni, se butti un occhio sul libro, il professor semeraro utilizza questo escamotage, prima inverte le sottostringhe "scomode" poi procede ad una sostituzione abbastanza "lineare", spero sia chiaro anche perchè rileggendo la grammatica che ho scritto mi sto accorgendo che è giusta |
|
|
|
ekkekkazz
Utente innocuo
|
Inserito il - 24/04/2006 : 18:07:55
|
| ma io non capisco... se, come dice lui, c'è il non determinismo nelle derivazioni, a questo punto posso creare delle parole che non stanno in L, e quindi L!=L(G) perchè L(G) non sta in L... |
|
|
|
ianus
Nuovo Utente
|
Inserito il - 24/04/2006 : 18:41:39
|
a questa obiezione ti posso rispondere solo in un modo.
giusto il fattore non deterministico, a parte il fatto che non mi sembra che siamo obbligati ad utilizzare grammatiche non deterministiche, anzi spesso e volentieri facciamo proprio il contrario, in secondo luogo....
IL SEMERARO E' LA LEGGE
chinati al suo cospetto 
a parte gli scherzi, magari èun linguaggio inerenetemente ambiguo |
Modificato da - ianus in data |
|
|
|
ekkekkazz
Utente innocuo
|
Inserito il - 24/04/2006 : 18:51:04
|
mah!... cmq rivedendo, con questa grammatica:
S->R|aba, R->(a)R(BA)|a(BA), AB->BA, AA->Aa, BB->Bb, aBb->abb, bAa->baa
non ho problemi di correttezza come quelli di prima, vero? ho fatto tutti i test, a me sembra di si... quindi per giustificare formalmente che L è CS si dovrebbe dim. la correttezza con la doppia inclusione... |
|
|
| |
Discussione |
|
|
|
(a^n)(b^n)(a^n)
