Laurea in informatica: Traduttori 1

[Matrixbob]

C'è qualcuno che s'intende di grammatiche generative o automi riconoscitivi per i linguaggi?!
Ho 1 esercizio corto corto che non mi torna :)

[nin]

Originariamente inviato da Matrixbob
C'è qualcuno che s'intende di grammatiche generative o automi riconoscitivi per i linguaggi?!
Ho 1 esercizio corto corto che non mi torna :)

Potresti spiegare diversamente cosa ti serve??

[Matrixbob]

Originariamente inviato da nin
Potresti spiegare diversamente cosa ti serve??
Stasera salvo correzioni del prof alle 16 a lezione te lo posto.
Sciau! :)

[dorzo]

Facce sapè
Ciao
:)

[Matrixbob]

Originariamente inviato da dorzo
Facce sapè
Ciao
:)
Allora, date le grammatiche:
[1]
S-->ASB | c
A-->a | b
B-->b | bb
[2]
S-->ASB | c
A-->a | aA
B-->b | bb

dire se sono regolari e perchè, ed in caso siano regolari dare la grammatica lineare destra che le genera.

[Matrixbob]

Originariamente inviato da dorzo
Facce sapè
Ciao
:)
Up!
L'interesse è già svanito?!

[jumpermax]

Originariamente inviato da Matrixbob
Allora, date le grammatiche:
[1]
S-->ASB | c
A-->a | b
B-->b | bb
[2]
S-->ASB | c
A-->a | aA
B-->b | bb

dire se sono regolari e perchè, ed in caso siano regolari dare la grammatica lineare destra che le genera.
A naso non sembrano regolari, visto che entrambe hanno self embedding.

[dorzo]

Originariamente inviato da Matrixbob
Up!
L'interesse è già svanito?!

Assolutamente no :)

[Matrixbob]

Originariamente inviato da jumpermax
A naso non sembrano regolari, visto che entrambe hanno self embedding.
L'autoinclusione non è una condizione sufficiente poichè queste grammatihe non siano regolari.
Occorre sviluppare il linguaggio e ragionarci sopra per capire se è regolare o meno.
Io sto cercando appunto una tecnica per non ragionarci troppo :)

[jumpermax]

Originariamente inviato da Matrixbob
L'autoinclusione non è una condizione sufficiente poichè queste grammatihe non siano regolari.
Occorre sviluppare il linguaggio e ragionarci sopra per capire se è regolare o meno.
Io sto cercando appunto una tecnica per non ragionarci troppo :)
A dire il vero sì. La grammatica che contiene self embedding è per definizione stessa di grammatica regolare, non regolare.
Poi resta da vedere se il linguaggio che genera è regolare oppure no, perché l'ambiguità delle regole può rendere la produzione col self embedding inutile e quindi eliminabile.
I due casi in questione invece non sono eliminabili, il primo in modo evidente dato che per ogni a prima di c deve esserci uno o 2 b dopo di di c. Non esiste modo per un automa di riconoscere un linguaggio del genere perchè serve memoria infinita per tenerne traccia.
Analogamente il secondo caso prevede che per ogni b o coppia di b dopo di c ci sia stata un a prima di c. Se ci fosse stata una produzione del tipo
B->b| bB
in aggiunta a quella con A si poteva eliminare il self embeddig.

[Matrixbob]

Originariamente inviato da jumpermax
A dire il vero sì. La grammatica che contiene self embedding è per definizione stessa di grammatica regolare, non regolare.
Poi resta da vedere se il linguaggio che genera è regolare oppure no, perché l'ambiguità delle regole può rendere la produzione col self embedding inutile e quindi eliminabile.
I due casi in questione invece non sono eliminabili, il primo in modo evidente dato che per ogni a prima di c deve esserci uno o 2 b dopo di di c. Non esiste modo per un automa di riconoscere un linguaggio del genere perchè serve memoria infinita per tenerne traccia.
Analogamente il secondo caso prevede che per ogni b o coppia di b dopo di c ci sia stata un a prima di c. Se ci fosse stata una produzione del tipo
B->b| bB
in aggiunta a quella con A si poteva eliminare il self embeddig.
Ok effettivamente a me interessava se li linguaggio era regolare e non la grammatica, per questo esercizio non si possono utilizzare gli automi riconoscitori.
CMQ buone le tue risposte.

[jumpermax]

Comunque credo che a parte la questione automa non esistono altri metodi per stabilire se un linguaggio è regolare oppure no. Il criterio della grammatica priva di self embedding come dicevi tu è sufficiente ma non necessario.

[Ziosilvio]

Originariamente inviato da jumpermax
Il criterio della grammatica priva di self embedding come dicevi tu è sufficiente ma non necessario.
Se non vado errato, come condizione necessaria c'è il Pumping Lemma.

[Matrixbob]

Originariamente inviato da jumpermax
Comunque credo che a parte la questione automa non esistono altri metodi per stabilire se un linguaggio è regolare oppure no.
A quanto pare esistono perchè noi gli automi li abbiamo iniziati oggi e gli esercizi che ho postato erano della prima parte del corso ;)

[Matrixbob]

Originariamente inviato da Ziosilvio
Se non vado errato, come condizione necessaria c'è il Pumping Lemma.
Si ok ... non ho capito niente.

[jumpermax]

Originariamente inviato da Matrixbob
A quanto pare esistono perchè noi gli automi li abbiamo iniziati oggi e gli esercizi che ho postato erano della prima parte del corso ;)
Beh mi sembra che tu nell'esercizio non abbia applicato un teorema ma piuttosto hai cercato di vedere "ad occhio" se il self embedding era eliminabile. Il pumping lemma citato credo dimostri la cosa altrettanto bene ma è l'analogo del ragionamento ad automi che facevo io.

[Matrixbob]

Originariamente inviato da jumpermax
Beh mi sembra che tu nell'esercizio non abbia applicato un teorema ma piuttosto hai cercato di vedere "ad occhio" se il self embedding era eliminabile.
No perchè non c'è nessun teorema, ma se sviluppando un po' il linguaggio o ragionandoci sopra riesci a trovare delle dipendenze funzionali, come ad esempio un bilanciamento con asse di crescita centrale, allora non può essere altro che una grammatica context free.

Originariamente inviato da jumpermax
Il pumping lemma citato credo dimostri la cosa altrettanto bene ma è l'analogo del ragionamento ad automi che facevo io.
Cosa sia questo pumping lemma non lo so propio ....

[Ziosilvio]

Originariamente inviato da Matrixbob
Cosa sia questo pumping lemma non lo so propio ....
Pumping Lemma:
Per ogni linguaggio regolare L esiste N>0 tale che, per ogni parola w appartenente ad L la cui lunghezza sia maggiore di N, esistono tre parole x, y, z sull'alfabeto di L tali che:
1) w = xyz;
2) y non e' la parola vuota;
3) x(y^n)z appartiene a L per ogni n.

ESERCIZIO: dimostrare il Pumping Lemma.
Suggerimento: sia N il numero di stati di un automa che riconosce L...

[Matrixbob]

Zio guarda se sai aiutarmi anche qui:
http://forum.hwupgrade.it/showthread.php?s=&threadid=815046
io non ho bene e idee chiare.