Newsgroup: it.scienza.informatica
Titolo: Grammatiche regolari e libere da contesto

Ciao, ho un grossissimo dubbio:
sono al primo anno di informatica e mi è stato detto che una
grammatica è regolare quando si ha un ordinamento totale dei non
terminali, quindi
A->aB
e non 
A->aA
Questo poi è stato smentito, addirittura dicendo che
A->AaB è una grammatica regolare quando all'inizio ci è stato detto
che le grammatiche regolari hanno al piu un non terminale a destra
della freccia.
C'è qualche bravo ragazzo tra di voi che ha la pazienza di spiegarmi
in due parole quali sono in realtà le grammatiche regolari e quali
sono libere da contesto?
Chiedo entrambi perche capita che la prof ci faccia trasformare una
grammatica regolare in una libera da contesto quando io trovo scritto
ovunque che una grammatica regolare è anche libera da contesto!!!
HELP!!!!!

 ovunque che una grammatica regolare è anche libera da contesto!!!
L'insieme delle grammatiche regolari e` sottoinsieme di quello delle 
grammatiche libere da contesto, quindi l'affermazione e` esatta.
-- 
Enrico `Trippo' Porreca

ovunque che una grammatica regolare è anche libera da contesto!!!
Hai ragione. Una g. regolare e' gia' una g. libera da contesto. Basta
guardare la forma delle produzioni.
Quindi non c'e' da fare nessuna trasformazione.
Non ha molto senso trasformare un tipo di grammatica in un'altro di
gerarchia maggiore. Al massimo vale la pena chiedersi se data una
grammatica e' possibile trasformarla in una di gerarchia minore.
Piu' usuale e' invece trasformare una grammatica di tipo n in un'altra
di tipo n diversa dalla prima, per poter beneficiare di semplicita' o
uniformita' nella trattazione.
Cio' e' ad esempio lo scopo delle trasformazioni nelle forme normali
quali quella di Chomsky, di Greibach, ecc.
-- 
Linux Registered User #181013
[Exokernels] Although one approach to eliminating bloated, buggy,
unreliable operating systems is to make them smaller, a more radical
one is to eliminate the operating system altogether.

grammatica e' possibile trasformarla in una di gerarchia minore.
Bada che per g. di gerarchia maggiore intendo un insieme contenitore
piu' ampio. Praticamente una grammatica G e' di gerarchia maggiore
rispetto alla grammatica H <==> G e' di tipo n e H di tipo k>=n
(sempre secondo Chomsky). Forse avrei dovuto usare il termine
"superiore" o "padre".
Viceversa per "gerarchia minore".


Per farvi vedere esattamente la questione vi scrivo un testo di un
esercizio che abbiamo fatto in un compitino:
Da un automa descritto dalla seguente tabella:
         a             b               c
0       1	          2                -
1       -             0	 	 1
2      3             -                 2
3      -              -                 -
con stato iniziale 0 e finale 0 e 3 viene richiesta la grammatica
regolare come:
{a,b,c}{S}S{S::=(ac*b)*(epsilon | bc*a)}
poi viene richiesta la trasformazione da regolare a libera eliminando
gli * e gli | e viene data come soluzione questa:
{a,b,c}{S,A,B,C}S{S::=AB   A::=epsilon   A::=aCbA  B::=epsilon
B::=bCa  C::=epsilon   C::=cC}
Grazie delle risposte!!!!

B::=bCa  C::=epsilon   C::=cC}
Queste produzioni sono corrette per la grammatica.
Sarebbe stato corretto, secondo quello che intendeva l'esercizio,
anche l'insieme delle produzioni di cui sopra.
Quello che mi turba abbastanza e' la frase "trasformazione da regolare
a libera eliminando gli * e gli |" 8-)
Una grammatica viene _definita ncessariamente da delle produzioni_,
non da una espressione (che sia o no regolare) con *, |, ecc.ecc.! Che
poi esiste una relazione di equivalenza tra g.r. e espressioni
regolari come dimostrato da Kleene, e quindi si possono ricavare le
produzioni, e' un altro conto!
Per analogia, sarebbe come se ti chiedessero quanti anni ha tuo padre,
e tu rispondessi "mia nonna paterna e' nata nel 1930 e ha avuto il
figlio unico all'eta' di 25 anni" :-D
Ciao


Scusate se vi scasso ancora...ok, i dubbi me li sono
chiariti...qualcuno di voi sa dove eventualmente posso trovare
dispense adeguatamente esaurienti sulla materia?
thanX!

dispense adeguatamente esaurienti sulla materia?
Trovi un link in un post precedente.
Ad ogni modo per domande come queste che ti potessero sembrare
minimamente retoriche e' sempre d'obbligo leggersi qualche thread
precedente, nonche' fare ricerche sul web o usenet. Potresti trovare
la soluzione ancor prima di riuscire compilare un post.
Ciao!
