Linguaggi, compilatori e modelli computazionali

Formattazione del testo

Quindi alla fine le due cose importanti sono le reduce che sono fatte sui simboli dopo la virgola, e soprattutto, i simboli dopo la virgola sono dati dal FIRST di tutto quello che viene dopo la variabile che vado a chiudere (es. ho A->b.CC/b vado a prendere il rst di tutto quello che viene dopo C, ovvero "C/b", quindi il rst di C in questo caso e quindi vado a vedere le produzioni per capire qual è, se non ce l'ho prendo b che il simbolo dopo la virgola).

Poi si fa la tabella, esattamente come con SLR ma quando si fanno le reduce non si deve prendere il follow della testa ma i simbolini dopo la virgola.

First e FollowFirst

Si guardano le teste delle produzioni, quindi se devo fare il rst di A guardo le produzioni che sono del tipo A->..., e prendo la prima cosa che c'è nel corpo (il rst del corpo) facendo attenzione nel caso ci sia un simbolo terminale prendo quello, se c'è epsilon prendo epsilon mentre se invece c'è una variabile devo vedere il suo rst.

e se è annullabile (ovvero se contiene espilon) in quel caso prendo il suo rst senza epsilon e vado a prendere anche rst del simbolo successivo e cosi via

Per prima cosa metto subito nei follow della variabile iniziale $ (l'unica cesta/insieme che non parte vuota)

Guarda questa volta i corpi delle produzioni, quindi se devo fare il follow di A guardo le produzioni del tipo ..->..A.., di questi corpi guardo cosa c'è dopo (in pratica il rst di tutto quello che c'è dopo) se ho un simbolo terminale prendo quello, se dopo A non ho niente oppure è annullabile allora prendo il follow della testa, se ho una variabile prendo il suo rst se è annullabile prendo il follow della testa

Fondamentale ricordarsi che queste ceste/insiemi possono essere modi caticontinuamente quindi bisogna fare più cicli per essere sicuri, anche perché se il follow di A dipende dal follow di S e poi S cambia devo aggiornarlo

NEI FOLLOW NON CI PUO ANDARE EPSILON

Analisi

Semantica

In un linguaggio di programmazione dobbiamo ancora capire che la frase scritta è corretta, dopo l'analisi lessicale e sintattica c'è quella semantica

Durante l'analisi semantica si analizzano due cose, correlare gli usi degli identificatori con le loro dichiarazioni (es identificatori non dichiarati oppure capire a quale identificatore mi riferisco), e il type checking

Per correlare l'uso degli identificatori con le loro dichiarazioni si usa la symbol table

L'obiettivo del type checking è riscontrare errori di tipo, dove un tipo individua un insieme di valori come per esempio interi, float, ecc ed è importante perché questo determina quali operazioni posso fare su questi valori (es radice quadrata su numeri negativi non posso)

Logica

Si fa la logica sia perché serve come base sia perché servirà per il model checking, in informatica serve ad esempio per esprimere proprietà (come nei

La logica è una teoria costruita sulla teoria degli insiemi. Ci sono tante logiche, quella proposizionale è solo una di queste ed è la base di tutte le logiche. In una logica qualsiasi c'è una sintassi e una semantica, una sintassi definita da un CFG (grammatica libera dal contesto), nella semantica ho la definizione di che cos'è un modello, ho un insieme di modelli, il modello è ciò a cui applico la mia formula (ad esempio il sistema distribuito di cui devo verificare se soddisfa la proprietà), quindi al modello applico la formula e vedo se la soddisfa o meno, il modello si può chiamare anche "interpretazione" oppure "valuation". Ricapitolando, per una qualsiasi logica, bisogna definire la sintassi, qual è l'insieme dei modelli e come sono fatti questi modelli, e definire quando è che un certo modello soddisfa una certa formula.

LOGICA PROPOSIZIONALE

Questa è un po' la logica di base.

qui i lessemi (o token) vengono chiamati proposizioni. Un modello, in questa logica, è una funzione che associa ad ogni simbolo proposizionale il valore Vero o Falso. Ci sono tabelle di verità, tra le quali AND, OR, NOT e la tabella di implicazione che è più difficile perché bisogna ricordarsi certe cose. LOGICA DEI PREDICATI (o del Primo Ordine) Questa è più espressiva, qui si introduce una struttura, qui si esprimono proprietà riguardo ad un universo di individui (è un po' come OOP nei linguaggi di programmazione dove si comincia a parlare di persone, cani, cavalli, ecc). Ci sono delle proprietà sempre vere e altre che dipendono dal modello. I modelli della logica dei predicati sono dati da A (universo di individui), C (insieme di costanti, per esempio dire chi è Socrate), F (funzioni che vanno mappate da individui ad altri individui) e P (predicati che sono funzioni booleane, dati n individui restituisce vero o falso). Datotime" visto come un albero di mondi. Le logiche temporali consentono di esprimere concetti come "in un certo momento nel futuro", "in ogni momento nel passato", "in ogni momento nel futuro", "in ogni momento tra due momenti specifici" e così via. Queste logiche sono utilizzate in diversi campi, come l'intelligenza artificiale, la verifica formale dei sistemi, la programmazione reattiva e la modellazione dei sistemi distribuiti. Un esempio di logica temporale è la logica temporale lineare (LTL), che permette di esprimere proprietà temporali su una sequenza di stati. Ad esempio, si può esprimere la proprietà "in ogni stato futuro, il predicato P è vero" utilizzando l'operatore LTL <G>P. Un altro esempio è la logica temporale a tempo lineare (CTL), che permette di esprimere proprietà temporali su un albero di stati. Ad esempio, si può esprimere la proprietà "in ogni cammino futuro, il predicato P è vero" utilizzando l'operatore CTL <AG>P. Le logiche temporali sono uno strumento potente per la specifica e la verifica dei sistemi, in quanto consentono di esprimere e ragionare sul comportamento temporale dei sistemi in modo preciso e formale.time" dove viene visto come un albero di mondi

LTSUn Labeled Transition System (LTS) è un NFA senza stati di accettazione perché non bisogna riconoscere stringhe ma bisogna rappresentare i possibili comportamenti di un sistema.

Una traccia è una sequenza di etichette, in altre parole è un cammino che parte dallo stato iniziale e ogni passo che si fa si incontra un'etichetta.

Una traccia massimale possono essere tracce infinite (cammino all'infinito) o che si bloccano (quando finisco in uno stato senza transizioni), vanno avanti finché posso.

I sistemi modellati da automi LTS sono solitamente "sistemi concorrenti".

I "process algebra" sono un modo naturale per rappresentare sistemi di questo tipo, un operatore fondamentale è l'operatore parallelo, ci sono diversi tipi di process algebra ma noi ne usiamo uno semplicissimo l'FSP, dove ogni singolo processo lo rappresentiamo con un LTS, vengono dati nomi agli stati e per

ognistato si descrivono le transizioni che lo stato può fare. FONDAMENTALE tutte le volte che non do un nome ad uno stato allora ne devocreare uno nuovo, gli stati NON vanno riusati! Stop è per definizione il processo che non ha vie d'uscita, che si blocca. Ogni processo termina col punto. Reti di Petri Oltre alle Process Algebra esiste un altro modo grafico per rappresentare gra camente i sistemi concorenti, le Reti di Petri. Nelle retri di petri esistono le "piazze" rappresentate con un cerchio, e le "transizioni" rappresentati con dei quadrati, le frecce sono chiamate "archi". Le piazze sono attive quando hanno token al loro interno, posso avere anche più token sulla stessa piazza. Ogni processo da quello che ho capito è rappresentato da un token, se ce ne sono 3 infatti ho 3 processi. Se sull'arco ho un numero vuol dire che richiede più token per quella richiesta se è un arco entrante, se invece è uscente allora ne.

produce quanti ne dice

Ogni transizione devo vedere gli archi entranti, se sono 2 devo attendere che siano pronti quei token perché si muoveranno entrambi

fi fi fi fi fi fi fi

La configurazione si chiama marking, e abbiamo sia quella iniziale che quella finale, in pratica è la foto della rete di petri

Il marking graph è l'LTS di tutte le possibili esecuzioni

Il marking iniziale è anche detto M0 e può essere rappresentato ad esempio M0=(1,1,1,0) dove sono segnati i numeri di token che ci sono in ogni piazza

Se si hanno dei cicli il marking graph è infinito e quindi si dice che la rete di petri è unbounded

Per dire se una cosa è vera o falsa, ad esempio "il filosofo 1 prima o poi mangerà" è falsa perché posso fare mangiare il 3 continuamente senza mai fare mangiare l'1

Macchine di Turing

Dopo aver imparato i linguaggi regolari e quelli liberi impareremo i linguaggi ricorsivi e quelli ricorsivamente enumerabili

che sono 2 classi ancora più esteseTuring si chiese, ma quali sono i principi fondamentali, le basi che servono per costruire un algoritmo che risolve un problema? I linguaggi risolvono tutti gli stessi problemi? Alcuni si e altri no?Lui ha creato un modello chiamato Turing Machine che risolve un qualsiasi problema intuitivamente calcolabile, ovvero risolvibile eseguendo una proceduraAnche una macchina di Turing è un automa ma più potente, prendiamo gli automi a pila e liberiamoli dal concetto di pila e prendiamo un "nastro", qui abbiamo il concetto di stato finale, abbiamo anche un alfabeto di input e un alfabeto del nastro, un simbolo blank (che indica la parte del nastro inesplorata)Il comportamento della macchina di turing è definito dicendo se sei in un certo stato e hai un simbolo sotto la testina allora fai questa cosa, che può essere un cambio di stato, la sostituzione del simbolo nella testina con un altro simbolo, un movimento della testina a

destra o a sinistra

La versione non deterministica della macchina di turing non aumenta il potere espressivo, quindi è equivalente a quella deterministica

In base alla tesi di turing qualsiasi algoritmo o procedura che ho in testa, riesco a esprimerla così

Quindi, riassumendo, la configurazione iniziale della macchina di turing è data da stringa in input sul nastro (attorno tutti blank), testina sul primo simbolo della stringa in input, poi a parte ho il mio programma con le transizioni da applicare, tutte le volte che sono in uno stato di accettazione la macchina di turing si ferma e accetta

Per una stringa w che non appartiene al linguaggio della macchina di turing possono succedere due cose, o si blocca in uno stato non finale, oppure continua a girare all'infinito senza mai raggiungere uno stato finale

I linguaggi riconosciuti da un macchina di turing sono detti