INSIEMI NUMERABILI

• L’analisi matematica introduce il concetto di insieme numerabile come insieme i cui elementi possono essere “contati”

ossia

• che possiede una funzione biettiva

f: N S • che mette in corrispondenza i numeri naturali con gli elementi dell’insieme.

INSIEMI NUMERABILI

• Insiemi che possiedono una funzione biettiva

f: N S • che mette in corrispondenza i numeri naturali con gli elementi dell’insieme.

1

2 3

4

INSIEMI RICORSIVAMENTE ENUMERABILI

• La nozione di computabilità porta a intro-durre un concetto più forte: quello di insieme ricorsivamente enumerabile (o semidecidibile)

INSIEMI RICORSIVAMENTE ENUMERABILI

• Un insieme S è ricorsivamente enumera-bile (o semidecidibile) se esiste un procedimento effettivo per costruirlo

ossia

• se esiste una Macchina di Turing T capace di computare la funzione di corrispondenza f: N S.

INSIEMI RICORSIVAMENTE ENUMERABILI

• Quindi, la funzione

f: N S • non deve soltanto esistere...

1

2 3

4

INSIEMI RICORSIVAMENTE ENUMERABILI

• Quindi, la funzione

f: N S • non deve soltanto esistere...

...deve essere computabile!

1

2 3

4

INTERPRETAZIONE

Dire che la funzione

f: N S

è computabile

significa dire che

l’insieme S può essere effettivamente costruito (per enumerazione) appunto calcolando elemento per elemento la funzione f.

INSIEMI RICORSIVAMENTE ENUMERABILI

ATTENZIONE

Il fatto che l’insieme S possa essere costruito

NON SIGNIFICA AFFATTO

che si possa decidere se un elemento appartiene all’insie-me stesso.

Quello è tutto un altro problema!!!

INSIEMI RICORSIVI (o DECIDIBILI)

• Il problema di decidere dell’appartenenza di un elemento a un insieme porta a introdurre un ultimo concetto: quello di insieme ricorsivo (o decidibile)

INSIEMI RICORSIVI (o DECIDIBILI)

• Un insieme S è ricorsivo (o decidibile) se la sua funzione caratteristica

è computabile

ossia...

f (x) =

1, se x S

0, se x S

INSIEMI RICORSIVI (o DECIDIBILI)

ossia...

• se esiste una Macchina di Turing capace di rispondere sì o no, senza entrare in un ciclo infinito, alla domanda se un qualsiasi elemento appartiene all’insieme.

INSIEMI RICORSIVI (o DECIDIBILI)

TEOREMA 1

Se un insieme è ricorsivo (decidibile) è anche ricorsivamente enumerabile (semidecidibile)

ma non viceversa

INSIEMI RICORSIVI (o DECIDIBILI)

TEOREMA 2

Un insieme S è ricorsivo (decidibile)

se e solo se • sia S• sia il suo complemento N-S

sono ricorsivamente enumerabili (semidecidibili)

VA BENE, PERÒ….

... perché ci interessa tanto??

INSIEMI & LINGUAGGI

I linguaggi di programmazione sono costruiti a partire da un certo alfabeto

e ogni linguaggio è caratterizzato dall’insieme delle sue frasi lecite.

INSIEMI & LINGUAGGI

I linguaggi di programmazione sono costruiti a partire da un certo alfabeto

e ogni linguaggio è caratterizzato dall’insieme delle sue frasi lecite.

Non ci basta che l’insieme delle frasi sia ricorsivamente enumerabile, cioè possa essere generato ...

(ossia, che si possano generare le frasi “previste”)

INSIEMI & LINGUAGGI

I linguaggi di programmazione sono costruiti a partire da un certo alfabeto

e ogni linguaggio è caratterizzato dall’insieme delle sue frasi lecite.

… è indispensabile anche poter decidere se una frase è giusta o sbagliata senza entrare in ciclo infinito

e ciò richiede che l’insieme delle frasi del linguaggio sia ricorsivo (decidibile).

INSIEMI & LINGUAGGI

Se così non fosse…

• il compilatore (o interprete) che deve tradurre le istruzioni del linguaggio in linguaggio macchina potrebbe non rispondere (entrando in un ciclo infinito) nel caso incontrasse una frase errata

mentre noi vogliamo che si fermi e segnali l’errore!

LINGUAGGI E PROPRIETÀ

Un linguaggio è un insieme di frasi Una frase è una sequenza di simboli

appartenenti a un certo alfabeto Un linguaggio deve essere

effettivamente generabile Un linguaggio di programmazione deve

essere decidibile

ALCUNE DEFINIZIONI

Alfabeto V (o vocabolario o lessico)• È l’insieme dei simboli con cui si

costruiscono le frasi

Universo linguistico V* di un alfabeto V• È l’insieme di tutte le frasi (sequenze

finite di lunghezza arbitraria) di elementi di V.

Linguaggio L su un alfabeto V• È un sottoinsieme di V*.

LINGUAGGI & GRAMMATICHE

Problema:• Come specificare il sottoinsieme di V*

che definisce il linguaggio?

Risposta:• Specificando il modo formale e preciso

la sintassi delle frasi del linguaggio• tramite una grammatica formale

GRAMMATICA FORMALE

Una quadrupla VT,VN,P,S dove: VT è un insieme finito di simboli terminali VN è un insieme finito di simboli non

terminali P è un insieme finito di produzioni, ossia

di regole di riscrittura S è un particolare simbolo non-terminale

detto simbolo iniziale o scopo della grammatica.

GRAMMATICA B.N.F.

Una Grammatica B.N.F. è una grammaticain cui le produzioni hanno la forma

X ::= Adove: X VN è un simbolo non terminale, e: A è una stringa, ossia una sequenza di

simboli ciascuno appartenente all’alfabeto V = VN VT.

FORMA B.N.F. COMPATTA

• Nel caso di più regole con la stessa parte sinistra:

– X ::= A1

– ....

– X ::= AN

• Per comodità si stabilisce allora di poterle compattare in un’unica regola:

X ::= A1 | A2 | .. | AN

• dove il simbolo | indica l’alternativa.

GRAMMATICA & LINGUAGGIO

Una Grammatica B.N.F. definisce quindi un linguaggio sull’alfabeto terminale VT mediante un meccanismo di derivazione (o riscrittura) .

GRAMMATICA & LINGUAGGIO

Data una grammatica G, si dice perciòLinguaggio LG generato da G

l’insieme delle frasi di V • derivabili dal simbolo iniziale S• applicando le produzioni P

GRAMMATICHE, LINGUAGGI & AUTOMI RICONOSCITORI

Grammatiche di diversa strutturacomportanolinguaggi con diverse proprietàe implicanoautomi di diversa “potenza computazionale”per riconoscere tali linguaggi.

CLASSIFICAZIONE DI CHOMSKY

Le grammatiche sono classificate in 4 tipi

in base alla struttura delle produzioni

• Tipo 0: nessuna restrizione sulle produzioni

CLASSIFICAZIONE DI CHOMSKY

Le grammatiche sono classificate in 4 tipi

in base alla struttura delle produzioni

• Tipo 1 (gramm. dipendenti dal contesto):produzioni vincolate alla forma:

x A y ::= x ycon x,y,VTVN)*, AVN,

In pratica, A può essere sostituita da solo nel contesto x A y.

Non si diminuisce mai la lunghezza della “forma di frase”corrente.

CLASSIFICAZIONE DI CHOMSKY

Le grammatiche vengono classificate in 4 tipi

in base alla struttura delle produzioni

• Tipo 2 (gramm. libere da contesto):produzioni vincolate alla forma

A ::= con AVN, VTVN)*-{}

Qui A può sempre essere sostituita da .

Caso particolare: grammatica lineare- se = u VT oppure = u B v, con u,v VT e B VN

CLASSIFICAZIONE DI CHOMSKY

Le grammatiche vengono classificate in 4 tipi

in base alla struttura delle produzioni

• Tipo 3 (grammatiche regolari):produzioni vincolate alla forma ricorsiva

A ::= a | aB (ricorsiva a destra)A ::= a | Ba (ricorsiva a sinistra)

con A,BVN, e aVT.

Si ottengono grammatiche rispettivamente lineari a destra olineari a sinistra.

CLASSIFICAZIONE DI CHOMSKY

In sintesi

• Tipo 0 (generiche)

• Tipo 1 (dipendenti da contesto)

• Tipo 2 (libere da contesto)

• Tipo 3 (regolari)

Gen

eral

ità

Sem

plicità A

utoma

riconoscitore

GRAMMATICHE & MACCHINE PER RICONOSCERE LINGUAGGI

• I linguaggi generati da grammatiche di tipo 1 (e quindi anche di tipo 2 e tipo 3) sono riconoscibili, ossia esiste un algoritmo per decidere se una frase appartiene o meno al linguaggio.

• Un tale procedimento non esiste invece,in generale, per grammatiche di tipo 0.

• Ma… CHI li riconosce?

GRAMMATICHE & MACCHINE PER RICONOSCERE LINGUAGGI

Tipo 3 Automa a Stati Finiti (ASF)

Tipo 2 Macchina a stack (ASF + stack)

Tipo 1 Macchina di Turing con nastro limitato

Tipo 0 SE è riconoscibile (può non esserlo), occorre una Macchina di Turing

AUTOMA A STATI FINITI

Un macchina astratta molto più semplice di una Macchina di Turing

niente nastro niente funzione di direzione, dfn() quindi, niente memoria illimitata!

per questo si chiama “a stati finiti” gli stati sono la sua unica forma di memoria che riassume la storia passata

spesso descritto con un grafo degli stati

AUTOMA A STATI FINITI

dove A = insieme finito dei simboli di ingresso e uscita S = insieme finito degli stati F = insieme finito degli stati finali (F S) mfn: A S A (funzione di macchina) sfn: A S S (funzione di stato)

Formalmente definito dalla quintupla:

A, S, F, mfn, sfn

AUTOMA A STATI FINITI: ESEMPIO

Riconoscimento di un identificatoreP = {

<id> ::= <lettera> { <lettera> | <cifra>}

<lettera> ::= A | B | C | D | ... | Z

<cifra> ::= 0|1|2|3|4|5|6|7|8|9}

Un identificatore corretto deve portare l’automa in uno stato finale di accettazione

Un identificatore errato deve portare l’automa in uno stato finale di errore

altro simbolo

AUTOMA A STATI FINITI: ESEMPIO

S0 S1

lettera

lettera o cifra

S2

cifra o altro simbolo

qualunque simbolo

stato finale di errore

stato finale di accettaz.

stato iniziale

SINTASSI & SEMANTICA

• Sintassi: dà le regole per scrivere frasi corrette

• Semantica: attribuisce significato alle frasi corrette

Attenzione:Non tutte le frasi sintatticamente corrette hanno anche significato

SINTASSI & SEMANTICA

Ad esempio, la grammatica:

P = {<frase> ::= <soggetto> <verbo> <compl-ogg><soggetto> ::= <articolo><nome><articolo> ::= il<nome> ::= gatto | topo | sasso<verbo> ::= mangia | beve<compl-ogg> ::= <articolo> <nome>

}consente anche di generarela frase “il sasso beve il topo”

…ma senza senso!

sintatticam.corretta...