Grammatiche regolari e libere da contesto

[Andrea]

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!!!!!

[Sephiroth]

Diario del Capitano. Data stellare: Thu, 13 Nov 2003 14:08:55 GMT.

Post by Andrea
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.

Una grammatica regolare e' una grammatica dove ogni produzione e' del
tipo:
A --> aB
oppure
A --> a
dove A, B sono simboli non terminali, e a e' simbolo terminale.

Le produzioni A-->aB e A-->aA non violano la grammatica regolare.
La produzione A-->AaB invece non puo' essere di una g.r., ma al limite
di una grammatica libera da contesto.
E' facile osservare che nelle parole intermedie, derivate durante
l'applicazione delle produzioni, i simboli terminali sono sempre a
sinistra, mentre i simboli non terminali a destra. E' forse questo
l'ordinamento che ti hanno suggerito?

Post by Andrea
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?

Le grammatiche libere da contesto sono quelle le cui produzioni sono
tutte del tipo:
A --> X
dove A appartiene ai simboli non terminali, e X appartiene all'insieme
di tutti i simboli, cioe' insieme dei terminali unito all'insieme dei
non terminali.
Vengono chiamate "libere da contesto" perche' applicando una qualunque
produzione A-->X:
BAC ==> BXC
ovvero il fattore A deriva X indipendentemente da cosa siano B e C,
cioe' i simboli adiacenti, chiamati contesto appunto.
Le grammatiche regolari vengono chiamate tali perche' vi e' una specie
di "regolarita'" dentro le parole del linguaggio, c'e' cioe' una sorta
di pattern che si ripete nella parola. Cio' e' piu' evidente se si
considera il lemma d'iterazione per i linguaggi regolari.

Post by Andrea
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!!!

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.

[Andrea]

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!!!!

[Sephiroth]

Diario del Capitano. Data stellare: Fri, 14 Nov 2003 20:19:19 GMT.

Post by Andrea
Per farvi vedere esattamente la questione vi scrivo un testo di un
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
{a,b,c}{S}S{S::=(ac*b)*(epsilon | bc*a)}

Suppongo
{a,b,c} simboli terminali
{S} simboli non terminali
S simbolo iniziale
* operatore star, ossia unione di tutte le potenze naturali
P = (S --> D,
A --> aC,
C --> cC,
C --> B,
B --> bD,
D --> A,
D --> epsilon,
D --> bE,
E --> cE,
E --> a) produzioni

(ac*b)*(epsilon | bc*a) non e' un insieme di produzioni, al massimo e'
un'espressione regolare. Non e' molto ortodosso partire definendo
l'insieme di simboli terminali, l'insieme dei non terminali, il
simbolo iniziale, e poi tirare fuori un'espressione regolare! :-)
Casomai l'espressione poteva essere usata per definire un linguaggio,
per i quali si usano gli operatori classici dell'algebra di Kleene:
unione, intersezione, ...

Post by Andrea
poi viene richiesta la trasformazione da regolare a libera eliminando
{S::=AB A::=epsilon A::=aCbA B::=epsilon
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

[Andrea]

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!

[Sephiroth]

Diario del Capitano. Data stellare: Mon, 17 Nov 2003 19:14:32 GMT.

Post by Andrea
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?

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!

[Sephiroth]

Diario del Capitano. Data stellare: Thu, 13 Nov 2003 21:19:13 +0100.

Post by Sephiroth
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.

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".

[Enrico `Trippo' Porreca]

Post by Andrea
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 [regola di produzione di una] grammatica regolare quando
all'inizio ci è stato detto che le grammatiche regolari hanno al piu
un non terminale a destra della freccia.

A->AaB *non* e` una regola di produzione di una grammatica regolare
(vedi sotto).

Post by Andrea
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?

Le grammatiche libere da contesto hanno sul lato sinistro di ogni regola
di produzione esattamente un simbolo non terminale.

Le grammatiche regolari sono libere da contesto (quindi anche qui si
puo` avere un solo non terminale sulla sinistra) e, come ulteriore
restrizione, sulla destra delle regole di produzione possono avere

a) un terminale
b) un terminale piu` un non terminale.

Post by Andrea
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!!!

L'insieme delle grammatiche regolari e` sottoinsieme di quello delle
grammatiche libere da contesto, quindi l'affermazione e` esatta.