[Linguaggi e Traduttori] Tipi di Linguaggi

[luxorl]

Ciao a tutti, sto studiando da poco la teoria dei linguaggi e sono arrivato alla distinzione dei linguaggi secondo Chomsky, quest'ultimo divide i linguaggi in quattro grandi insiemi ognuno sottoinsieme di quello che lo precede...

Tipo 0 Grammatiche Illimitate
Tipo 1 Grammatiche Sensibili al Contesto
Tipo 2 Grammatiche Context Free
Tipo 3 Grammatiche Lineari o Regolari

ora veniamo ai miei dubbi.. una grammatica di tipo 0 è definita come
(def. presa dai lucidi del mio corso)

alfa ---> beta

con alfa appartente V*°VN°V*
e beta appartenente V*

(Dove V è l'insieme dei simboli terminali e VN dei non terminali)

Domanda 1) La notazione °VN° cosa significa precisamente?
che alfa appartiene a V* oppure VN oppure V*? :what:

Passiamo al secondo dubbio:

Nella definizione delle grammatiche di tipo 1: (Sensibili al contesto)

alfa ---> beta

con alfa appartenente V*°VN°V*
e beta appartenente V+

|alfa|<=|beta|

Domanda 2) Quest'ultima regola: "|alfa|<=|beta|" che significa precisamente?
modulo di alfa minore uguale di modulo di beta, cioè cardinalità di alfa minore uguale di cardinalità di beta, cioè numero di simboli di alfa minore uguale a numeri di simboli di beta? :what:


Grazie a chiunque vorrà darmi un aiutino :) :mano:

[misterx]

* è la chiusura di klenee ?

[pietro84]

puoi postare il link ai lucidi? mi interessa quest'argomento...

[luxorl]

* è la chiusura di klenee ?

Si :)

[luxorl]

puoi postare il link ai lucidi? mi interessa quest'argomento...

Sono su un sito con log-in tramite matricola e password..
I lucidi sono un bel po' comunque magari in pvt dammi una mail che quando ho tempo li scarica e te li passo ;)

[jumpermax]

Ciao a tutti, sto studiando da poco la teoria dei linguaggi e sono arrivato alla distinzione dei linguaggi secondo Chomsky, quest'ultimo divide i linguaggi in quattro grandi insiemi ognuno sottoinsieme di quello che lo precede...

Tipo 0 Grammatiche Illimitate
Tipo 1 Grammatiche Sensibili al Contesto
Tipo 2 Grammatiche Context Free
Tipo 3 Grammatiche Lineari o Regolari

ora veniamo ai miei dubbi.. una grammatica di tipo 0 è definita come
(def. presa dai lucidi del mio corso)

alfa ---> beta

con alfa appartente V*°VN°V*
e beta appartenente V*

(Dove V è l'insieme dei simboli terminali e VN dei non terminali)

Domanda 1) La notazione °VN° cosa significa precisamente?
che alfa appartiene a V* oppure VN oppure V*? :what:

Passiamo al secondo dubbio:

Nella definizione delle grammatiche di tipo 1: (Sensibili al contesto)

alfa ---> beta

con alfa appartenente V*°VN°V*
e beta appartenente V+

|alfa|<=|beta|

Domanda 2) Quest'ultima regola: "|alfa|<=|beta|" che significa precisamente?
modulo di alfa minore uguale di modulo di beta, cioè cardinalità di alfa minore uguale di cardinalità di beta, cioè numero di simboli di alfa minore uguale a numeri di simboli di beta? :what:


Grazie a chiunque vorrà darmi un aiutino :) :mano:
a) credo sia la concatenazione
b) le trasformazioni sulle stringhe non comportano un accorciamento delle medesime. Nota che beta appartiene a V+ (non ci sono trasformazioni verso la stringa vuota)

[jumpermax]

X luxorl

Sei sicuro che V sia l'alfabeto dei terminali e non l'unione tra terminali e nonterminali? Non ha senso, ad esempio nel primo caso, che beta sia V* dato che può avere ovviamente anche nonterminali come nelle context free...

Cmq

1) ° Indica la concatenazione...quella regola significa che alpha deve contenere un nonterminale, preceduto o seguito da n simboli qualunque (se come credo V non indica quello che dici tu)

2) Indica quello che hai dedotto, ovvero "regole di lunghezza non decrescente". Ciò consente alle gramamtiche context sensitive di avere come automa riconoscitore una Macchina di Turing con un nastro della lunghezza della stringa da riconoscere, invece che infinito. Ovvero è possibile definire un algoritmo di riconoscimento della grammatica, che diventa un problema calcolabile...il che non è poco ;)
battuto sul tempo, e sulla qualità della risposta.... chapeau! ;)

[pietro84]

Non ho lucidi ma ottimi libri da consigliarti :D

- Linguaggi Formali e Artificiali di Crespi/Reghizzi (in italiano, molto valido)

Mentre questo:

- Compilers: principles, techniques, and tools by Aho, Sethi, Ullman

Va un po' oltre come argomenti...però... :ave: :ave: :ave: (come si intuisce dagli autori credo :D ).
Il secondo per "darci un'occhiata" diciamo che te lo puoi procurare...in vari modi con facilità :fiufiu:


P.S. Non è che volevi iscriverti ad Informatica ed hai sbagliato a compilare il foglio? :D

P.S.2: Il Crespi costa meno di 20€...molto ben spesi ;)


ok... comprerò il Crespi :D
grazie ;)
l'informatica non è che mi interessa molto culturalmente,se non in alcuni aspetti,come AI,programmazione parallela,algoritmi di ottimizzazione,computer vision,sistemi real time,progetto di architetture,inf teorica.
io ero iscritto a elettronica, poi mi sono appassionato all'automatica e son passato a ing inf a cui afferisce questo indirizzo.
questi argomenti mi incuriosiscono e sono più interessanti degli esami tipo data base, sistemi informativi(che poi ho studiato per lavoro)

[pietro84]

Abbiamo gusti simili vedo Anche architetture mi interessa, ma + di un'infarinatura non ho e non avrò mai dato che è approfondita in una magistrale che non ho scelto (e cmq si fa molto + ad ingengeria).

sì a ingegneria si fa molta progettazione di architetture(alla magistrale però), visto che si approfindisce anche l'elettronica e la parte di elettromagnetismo che spiega il funzionamento fisico dei circuiti.
informatica approfondisce molto di più la parte di informatica teorica,di cui io ho solo un'infarinatura e non tratterò alla specialistica :)
penso che la differenza tra le due lauree stia proprio alla specialistica principalmente.

Visto che ti interessano i problemi di ottimizzazione, conosci AMPL?

l'ho sentito nominare ma non l'ho mai usato, per risolvere problemi di ottimizzazione ho usato il matlab o il C (nella tesi,perchè avevo dei requisiti di velocità da soddisfare). cmq l'anno prossimo ho un corso più specifico sull'ottimizzazione e mi pare che si usi proprio questo sw oltre al matlab.

Mooolto di più, concordo. il "problema" è che per alcuni argomenti l'unico sbocco (o quasi) è la ricerca... A me l'idea piace, però mi rendo conto delle difficoltà in Italia soprattutto...

sì infatti...fuori dalle università non c'è niente.
io vorrei provare nel mondo dei controlli automatici a cercare qualcosa di interessante. chissà... la situazione non è tanto rosea :)

[luxorl]

X luxorl

Sei sicuro che V sia l'alfabeto dei terminali e non l'unione tra terminali e nonterminali? Non ha senso, ad esempio nel primo caso, che beta sia V* dato che può avere ovviamente anche nonterminali come nelle context free...

Cmq

1) ° Indica la concatenazione...quella regola significa che alpha deve contenere un nonterminale, preceduto o seguito da n simboli qualunque (se come credo V non indica quello che dici tu)

2) Indica quello che hai dedotto, ovvero "regole di lunghezza non decrescente". Ciò consente alle gramamtiche context sensitive di avere come automa riconoscitore una Macchina di Turing con un nastro della lunghezza della stringa da riconoscere, invece che infinito. Ovvero è possibile definire un algoritmo di riconoscimento della grammatica, che diventa un problema calcolabile...il che non è poco ;)


Hai ragione V è l'uonione dei non terminali e dei terminali..
Grazie delle risposte e della correzione ;)

[r_howie]

Come ti hanno già risposto,
1) concatenazione;
2) | | indica la cardinalità (lunghezza) di una stringa.

Vedi se ti aiuta o ti confonde il seguente schema:
http://img212.imageshack.us/img212/8135/chomsky1ox.th.jpg (http://img212.imageshack.us/my.php?image=chomsky1ox.jpg)

[pietro84]

Bene, così potrai provare la GUI per AMPL che sto sviluppando per la tesi :D

certo se mi faranno usare AMLP la proverò senz'altro, specialmente se mi manderai la tesi o una buona documentazione del sw :D

[pietro84]

:D Ci riaggiorniamo poi allora :)

ok ;)