Schemi teoria Fondamenti di informatica

È una macchina di Turing non deterministica

con limite sulla dimensione del nastro, il AUTOMA LIMITATO LINGUAGGI DI TIPO 3 (PRODUZIONI Sono riconosciuti da macchine a stati finiti (

nastro è limitato alle sole celle contenenti l' LINEARMENTE (LBA) REGOLARI) FSM)

input. Questi automi riconoscono tutti e soli i

linguaggi contestuali di tipo 1 LINGUAGGI DI TIPO 2 (PRODUZIONI NON Sono riconosciuti da automi a pila non

CONTESTUALI) deterministici (NPDA)

RICONOSCIMENTO DEI LINGUAGGI LINGUAGGI DI TIPO 1 (PRODUZIONI

È un automa con una testina di scrittura/ Automi limitati liberamente (LBA)

CONTESTUALI)

lettura su nastro bidirezionale "illimitato". Ad

ogni passo si trova in un certo stato e legge il Sono riconosciuti da macchine di Turing (

simbolo sul nastro, in base alla forma di TM). Questi linguaggi sono i più liberi e

transizione (deterministica) scrive un simbolo LINGUAGGI DI TIPO 0 (PRODUZIONI DI TIPO quindi l'unica cosa che una TM può fare è,

sul nastro, sposta la testina di una posizione GENERALE) data una stringa appartenente al linguaggio,

e cambia stato dire se questa stringa appartiene. In tutti gli

Σ altri casi potrebbe andare in un loop infinito

è l'alfabeto del nastro

Q è un insieme finito di valori Queste macchine passano da uno stato all'

MACCHINA DI TURING Un automa è una macchina astratta che

q_0 è lo stato iniziale TM deterministica altro a seconda dell'input e dell'output

realizza un certo algoritmo secondo un Σ

modello di calcolo

F è l'insieme di stati finali è l'alfabeto di input

δ è la funzione di transizione Q è l'insieme, non vuoto di stati

δ

AUTOMI E CALCOLO

La macchina non deterministica ha la stessa è la funzione di transizione che in base allo

potenza computazionale di quella stato attuale e al simbolo di input attuale mi

deterministica, però quella deterministica determina lo stato successivo

TM non deterministica

deve fare una singola elaborazione alla volta

e quindi ci mette molto più tempo rispetto ad q0 è lo stato iniziale

una non deterministica F è l'insieme di stati finali

In fomra NON DETERMINISTICA permette di Questo comporta che si può accedere solo

riconoscere i linguaggi non contestuali alla cima della pila, che si può leggere il Sono simili a FSM ma dotati di MEMORIA

simbolo in cima e che è possibile la INFINITA, organizzata a pila

In FORMA DETERMINISTICA permette di sostituzione del simbolo in cima con una

riconoscere i linguaggi non contestuali nuova stringa

deterministici Σ è l'alfabeto di input

Γ In particolare questa è la rappresentazione

è l'insieme di simboli della pila Con la TABELLA DI TRANSIONE della macchina:

La rappresentazione della funzione di

MACCHINA A STATI FINITI (FSM) transizione si può fare in due modi:

z_0 è il simbolo di pila iniziale

Q è l'insieme finito non vuoto di stati DEFINIZIONE DI PDA

q_0 stato iniziale AUTOMI A PILA

F insieme di stati finiti

δ è la funzione di transizione. In base allo Con il DIAGRAMMA DEGLI STATI

stato, al simbolo di input, al simbolo in cima

alla pila, determina lo stato successivo e i

simboli inseriti nella pila. Per rimuovere il Ci sono delle macchine non deterministiche

ε

simbolo in cima alla pila si scrive in cui, dato lo stato attuale ed un certo

simbolo di input la macchina può fare delle

1. Simbolo A in cima alla pila sostituito da BA, transizioni. Quindi dato uno stato attuale ed

FSM NON DETERMINISTICA

stato interno q un simbolo di input produce un INSIEME DI

Es. δ

Ho due transizioni _n è la funzione di transizione STATI SUCCESSIVI, ma non si sa in quale

ε vada. Dobbiamo immaginare che la macchina

2. Simbolo A eliminato (sostituito da ), generi tutti gli stati successivi

nuovo stato interno r PDA non deterministico (NPDA)

La NPDA ha maggiore potere Per ogni stato/ingresso vengono definiti stati

computazionale di PDA successivi

Il non determinismo aggiunge potere

EQUIVALENZA FSM/NFSM computazionale

FSM è una caso particolare di NFSM

COSTANTE Il numero di operazioni non dipende da n

SOTTO-LINEARE Un algoritmo è efficiente fino alla classe

Il numero di operazioni è proporzionale a n,

LINEARE polinomiale, un problema è trattabile se

ricerca lineare esiste un algoritmo efficiente

SOVRA-LINEARE

CLASSI DI

COMPLESSITÀ POLINOMIALE ESPONENZIALE

COMPLESSITÀ ESPONENZIALE SUPER-ESPONENZIALE

PROBLEMI P Esiste un algoritmo deterministico polinomiale

Non esiste un algoritmo deterministico

PROBLEMI P E NP polinomiale. Sulle macchine deterministiche

non è noto un algoritmo polinomiale per la

PROBLEMI NP ricerca di una soluzione, ma un algoritmo

polinomiale per la VERIFICA DELLA

SOLUZIONE Restituiscono automaticamente la memoria

per gli oggetti/dati che non servono più. I È una notazione formale e non ambigua per

vantaggi sono che si libera sistematicamente definire algoritmi, un algoritmo è una

della memoria, non si rimuovono dati ancora sequenza di istruzioni per risolvere un dato

SISTEMI DI GARBAGE COLLECTION

utili e che i dati vengono rilocati per problema

LINGUAGGIO DI

compattare la memoria. Gli svantaggi sono la

maggiore occupazione del processore e Lessico

È l'insieme di regole formali per scrivere frasi

PROGRAMMAZIONE

della memoria ben formate. Spesso la sintassi opera a due

SINTASSI livelli Struttura

Ogni linguaggio è caratterizzato da Attribuisce un significato alle frasi costruite

Traduzione del linguaggio in linguaggio SEMANTICA

COMPILATORE nel linguaggio

macchina COMPILATORI

Collegamento con librerie di supporto Lessicale

Libreria inclusa nel file oggetto, eseguibile

stand-alone FRONT-END Analisi del linguaggio di alto livello Grammaticale

LINKER

STATICO

Dimensioni maggiori, ma possibile includere Contestuale

ARCHITETTURA DEL

solo funzionalità utilizzate Collega i diversi moduli oggetti e il COMPILATORE RAPPRESENTAZIONE INITERMEDIA AST (Annotated Syntax Tree)

Il codice oggetto non è ancora eseguibile, un

collegamento può essere statico o dinamico

Librerie condivise da diverse applicazioni ESECUZIONE DEI PROGRAMMI

programma ad alto livello ha bisogno di

Per i PROGRA