Linguaggi, compilatori e modelli computazionali

Linguaggi, compilatori e modelli computazionali

Linguaggi di programmazione

È uno strumento che serve per descrivere in modo rigoroso come risolvere problemi, in modo che questi possano essere risolti da un esecutore automatico (in questo caso la CPU). Il compilatore trasforma il programma in codice oggetto che è poi eseguibile dalla CPU del computer, invece l'interprete traduce al volo. Il primo compilatore è del '54, fatto per il Fortran, ci hanno messo 18 anni uomo ma visto che erano un team ce ne hanno messi 3, è stato scritto in linguaggio macchina.

La differenza tra assembly e linguaggio macchina è che il primo si scrive un file di testo mentre il secondo è una memoria fatta di byte o di word che contengono codice binario. Self-hosting è compilare un linguaggio con un compilatore scritto col linguaggio stesso. Linguaggi Turing-equivalenti credo significhi che posso esprimere le stesse cose con linguaggi differenti.

Il lessico si riesce a determinare con un automa a stati finiti, la sintassi no e ha bisogno di altra memoria ausiliaria che dipende dalla lunghezza della stringa in input. Con gli automi a pila riesco a capire quante parentesi si sono aperte.

Concetti

Alfabeto è un insieme finito e non vuoto di simboli come per esempio l'alfabeto binario (0,1) oppure quello composto solo da lettere maiuscole. Una stringa è una sequenza finita di simboli da un alfabeto. Stringa vuota è una stringa con 0 occorrenze. La lunghezza di una stringa è il numero di posizioni per i simboli nella stringa, es. 0110 ha lunghezza = 4.

Potenze di un alfabeto sono l'insieme di delle stringhe di lunghezza k con i simboli dell'alfabeto. L'insieme di tutte le stringhe di un alfabeto è denotato da alfabeto stella di Kleene. Alfabeto + è dato da tutto tranne la stringa vuota, ovvero alfabeto stella di Kleene tranne stringa vuota. Con la concatenazione viene aggiunta una seconda stringa alla prima.

Un linguaggio è un insieme delle parole corrette, per esempio l'insieme delle parole italiane legali (linguaggio finito), l'insieme dei programmi C legali, l'insieme delle stringhe che consistono di n zeri seguiti da n uni (linguaggio infinito), linguaggio vuoto che non ha stringhe, insieme dei numeri binari il cui valore è primo (infinito). Un alfabeto sigma è sempre finito.

Automi e linguaggi regolari

Un DFA è un automa a stati finiti deterministici ed è una quintupla, col disegno è più visibile della tupla. Un automa identifica un linguaggio su di un alfabeto, identifica le parole accettate, è un sottoinsieme di sigma stella (che sono tutte le stringhe possibili), se do in pasto ad un automa una stringa mi dice se viene accettata.

Si dice deterministico perché in ogni stato c'è una e una sola transizione per ogni simbolo dell'alfabeto. Se si dà la stringa vuota all'automa non si esce dallo stato iniziale, e nel caso coincida con lo stato di accettazione allora finisce. Nell'esercizio che accetta tutte e sole le stringhe con numero pari di zero e di uni, ci sono 4 stati: ovvero il caso di pari zeri e uni, dispari zeri e uni, pari zeri e dispari uni, dispari zeri e pari uni.

Un NFA è un automa a stati non deterministici, anche qui come nel DFA è una quintupla ma cambia solo la funzione di transizione. Il bloccarsi è un concetto che qui esiste, infatti possono esserci degli stati in cui dando un input non si va avanti. Per ogni NFA c'è un DFA che è equivalente, equivalente significa che il linguaggio è lo stesso. La transazione epsilon non "mangia" nulla dalla stringa. L'epsilon closure di uno stato sono gli stati che posso raggiungere con transazioni epsilon compreso lo stato stesso.

Durante l'esercizio conviene segnarsi la epsilon closure di tutti gli stati perché verranno riutilizzati spesso. Gli stati di accettazione in un esercizio da NFA a DFA sono quegli stati che contengono almeno uno stato di accettazione. Se un linguaggio è esprimibile con un DFA allora è esprimibile anche con un'espressione regolare, questo non significa che tutti i linguaggi siano esprimibili con un DFA. I linguaggi regolari sono quei linguaggi esprimibili con DFA, NFA o espressioni regolari.

Espressioni regolari

Le espressioni regolari sono fatte da elementi di base che sono: epsilon, insieme vuoto, i simboli a dell'alfabeto, +, concatenazione che è il punto che si può anche non scrivere, stella di Kleene, e le parentesi per raggruppare. La stella di Kleene ha precedenza rispetto alla concatenazione che a sua volta ha precedenza rispetto al +, perciò 01* sono le stringhe che iniziano con 0 e poi hanno un numero arbitrario di uni, infatti in questo caso la stella di Kleene si riferisce solo all'1.

Da un NFA posso trovare un'espressione regolare corrispondente, e dall'espressione regolare posso trovare l'epsilon NFA corrispondente. L+ è come fare LL* ovvero L concatenato a L*, infatti L+ significa prenderlo almeno una volta, invece * è arbitrario che vale anche 0. Epsilon è l'elemento neutro della concatenazione. La concatenazione non è commutativa.

La differenza tra codice assembler e codice oggetto è che il primo è ancora testuale (ho un file di testo con delle istruzioni) mentre il secondo è binario (ha solo numeri, 0 e 1). La differenza tra codice sorgente assembler e C è che il primo ha una sintassi più semplice.

Conversioni e algoritmi

Per l'esame quando chiede di calcolare LL(1) o SLR(1), si prende la grammatica si calcolano i first e i follow (i first servono per calcolare i follow), se è SLR(1) dopo first e follow si può fare l'automa e costruire la tabella (vedendo se ci sono multiple entry), se chiede LR(1) i first e i follow non vanno calcolati subito ma dopo (durante la costruzione dell'automa).

DFA -> RE
Da DFA a espressioni regolari, tramite l'eliminazione degli stati. Di uno stato si considerano i suoi predecessori e i suoi successori ma si ignorano gli eventuali autocicli su di esso, si lavora prendendo tutte le coppie predecessori e successori tutti e si applica la formula.

Se ho ad esempio 3 stati di accettazione, li faccio tutti uno alla volta eliminando tutti gli altri stati tranne lui e lo stato iniziale, poi faccio la stessa cosa con gli altri stati di accettazione. Questo algoritmo si può applicare anche agli NFA. La stella di Kleene fa in modo che io possa fare quelle cose quante volte voglio. Non esistono modi matematici per dimostrare che una espressione è ulteriormente semplificabile, invece in un DFA c'è un modo per capire il minimo numero di stati per riconoscere uno stesso linguaggio.

Da espressioni regolari a epsilon-NFA è molto più facile. Non so perché nell'esempio di laboratorio lo fa con un NFA, comunque la prima cosa da fare è se ho più transizioni fra due stati unirle con dei "+" ad esempio "a+bb", poi all'inizio è comodo eliminare tutti gli stati che non sono né di accettazione e né iniziali, per eliminare uno stato faccio tutte le sue coppie di predecessori e successori, poi per ogni coppia prendo intanto le transizioni dirette già esistenti e le sommo quindi se ho pred-succ q0-q2 che hanno già un transizione diretta b allora faccio b+, poi considero il cammino che passa per lo stato che elimino (in questo caso q1) e prendo quindi a (che va da q0 a q1) poi gli eventuali autocicli su q1* (se non c'è prendo epsilon quindi non scrivo niente, se c'è ci devo mettere la stella *) ed infine l'ultimo pezzo del cammino (che va da q1 a q2) che in questo caso è a, alla fine si ottiene b+aa, una volta eliminato uno stato devo poi aggiornare il tutto con quello che ho ottenuto da predecessori e successori, infine rimango con uno stato iniziale e uno finale collegati da una transizione, e uso la formula (quella che il prof chiama del laghetto), IMPORTANTE se ho più stati di accettazione devo fare la somma di quello che ottengo per ogni coppia stato iniziale-stato di accettazione. Se ho lo stato iniziale se coincide con l'unico stato di accettazione allora devo rimanere solo con quello ed è un caso speciale.

CFG e PDA

CFG -> PDA (pila vuota)
Un unico stato con tutti autocicli del tipo epsilon/simboloDaSostituire/SimboloNuovo per ogni regola della grammatica, poi bisogna aggiungere una transizione per ogni simbolo dell’alfabeto per spilare del tipo a/a/epsilon.

PDA (pila vuota) -> PDA (stato finale)
Simile a quella di prima (tranne per le transizioni finali), si aggiunge un nuovo stato iniziale e finale ed anche un nuovo simbolo X, e fare che tutti gli stati dell’automa precedente vadano nello stato di accettazione se rilevano che c’è questo simbolo X (che vuol dire che la pila si svuotava), questa volta il nuovo stato finale è importante che sia di accettazione, come prima dal nuovo stato iniziale al vecchio faccio epsilon/X/ZX, e poi da ogni stato precedentemente dell’automa devo fare una transizione del tipo epsilon/X/epsilon che nel caso la pila sia vuota mi porta allo stato di accettazione.

PDA (stato finale) -> PDA (pila vuota)
Aggiungo un nuovo stato iniziale ed uno finale (anche se non sarà di accettazione, visto che qui non esistono), dal nuovo stato iniziale al vecchio stato iniziale creo una transizione che ha epsilon/X/ZX (X è una nuova variabile che starà addirittura sotto Z), poi per ognuno dei vecchi stati finali parte una transizione al nuovo stato che ho creato in fondo per ogni simbolo compresi Z e X del tipo epsilon/X/epsilon, poi creo pure autocicli nel nuovo stato finale (non di accettazione eh) con lo stesso sistema dove per ogni simbolo compresi Z e X del tipo epsilon/X/epsilon (anche se verranno delle transizioni inutili, quest’ultimo è come un aspirapolvere che ripulisce la pila).

PDA -> CFG
Non lo so fare.

Pumping lemma e linguaggi regolari

Non tutti i linguaggi sono esprimibili da DFA, NFA, espressioni regolari, ecc. Quelli che lo sono si chiamano linguaggi regolari. 0^n1^n non è regolare perché prendendo una stringa sufficientemente lunga di zeri si potrebbe finire la memoria dell'automa. Ci sono vari metodi per capire se un linguaggio è regolare oppure no, il metodo principale è il Pumping Lemma, infatti questo esprime delle proprietà che tutti i linguaggi regolari soddisfano.

Ogni stringa w del linguaggio la cui lunghezza è >= n quindi verrà toccato almeno due volte uno stesso stato, n che sono il numero degli stati dell'autonoma, m è invece la lunghezza della stringa w. La stringa w può essere scomposta in 3 stringhe, chiamate x, y, z che sono concatenate quindi w=xyz, y sicuramente non sarà mai vuota perché altrimenti non toccherei mai lo stesso stato, la lunghezza di xy è sicuramente <= n, per ogni k>=0 xy^kz appartiene al linguaggio ovvero vale la proprietà di pompaggio.

Il testo del teorema dice che se ho un linguaggio regolare e ho almeno una stringa accettata di lunghezza >= del numero di stati n del DFA che riconosce questo linguaggio, nel linguaggio regolare non ho solo quella stringa ma ho dimostrato che è infinito perché al linguaggio appartengono tutto un altro insieme di stringhe che si ottengono pompando la parte di stringa che nell'automa forma un ciclo.

IL PUMPING LEMMA NON SI USA PER DIMOSTRARE CHE UN LINGUAGGIO È REGOLARE MA PER DIMOSTRARE LA NON REGOLARITÀ', davanti ad un linguaggio c'è un bivio se penso che sia regolare provo a costruire un DFA o un'espressione regolare e così dimostro che è regolare se ci riesco, se invece penso che non sia un regolare allora provo a dimostrare che non lo è facendo vedere che la condizione necessaria è violata e utilizzando il Pumping Lemma per fare una dimostrazione per assurdo.

Per utilizzare il pumping basta trovare una w ovvero una stringa che frega il Pumping Lemma. Nell'applicare il pumping lemma ho due gradi di libertà, uno nella scelta della stringa e uno nella scelta del pompaggio (ovvero quale valore dare a k). Quindi riassumendo, scelgo una stringa che appartiene al linguaggio e che sia sufficientemente lunga che mi generi un ciclo quindi deve essere lunga >= n (numero degli stati), poi ragiono su tutte le possibili scomposizioni di questa stringa (non scelgo io come verrà scomposta in xyz) però posso scegliere io il k e devo dimostrare che applicando questo k esco dal linguaggio.

Linguaggi liberi

Come nei linguaggi regolari ci sono le espressioni regolari, nei linguaggi liberi ci sono le grammatiche in particolare si chiamano grammatiche libere dal contesto (CFG), queste grammatiche consentono di esprimere classi più grandi dei linguaggi regolari. Oltre che le grammatiche libere dal contesto esistono anche le dipendenti dal contesto. ANTLR è il tool che consentirà di programmare compilatori.

Una stringa palindroma è una stringa che w = reverse (w), ovvero la stringa letta al contrario. Le casistiche sono due, quando le lettere sono pari oppure dispari es "otto" e "ara", una ha lo specchio in mezzo e uno nella "r". Una grammatica libera dal contesto è una quadrupla formata da: un insieme di variabili V, un insieme di terminali T (che è l'alfabeto del linguaggio che la grammatica genera), P che sono le produzioni e sono come le transizioni per gli automi, S dove indico quale delle variabili è quella iniziale.

Per le derivazioni si usa seguire la regola del rimpiazzare sempre la variabile più a sinistra oppure quella più a destra. Quindi un linguaggio libero dal contesto è un linguaggio esprimibile da grammatiche libere dal contesto, esattamente come i linguaggi regolari sono i linguaggi che si possono esprimere tramite automi a stati finiti, espressioni regolari, ecc.

Un albero sintattico è innanzitutto un albero, avendo una stringa di un linguaggio posso rappresentarlo sotto forma di albero, gli alberi sintattici sono una rappresentazione alternativa alle derivazioni, può capitare di avere una grammatica le cui stringhe abbiano più alberi sintattici ma questo è male perché vorremmo che sia unico, esistono infatti alcune grammatiche ambigue dove non posso rimuovere l'ambiguità. Ogni nodo interno (ovvero non foglia) deve essere per forza variabili, ogni foglia invece deve essere etichettata o con variabili o con simboli terminali dell'alfabeto o con epsilon, se una foglia è etichettata con epsilon allora questa non deve avere fratelli (unico figlio del suo genitore).

Il prodotto di un albero sintattico è la stringa di foglie da sinistra a destra. Il problema dell'ambiguità nasce quindi quando una stringa del linguaggio della grammatica è il prodotto di più alberi sintattici diversi fra loro, allora ci sarà un grammatica ambigua. Il problema non è avere tante derivazioni ma avere tanti alberi. Una grammatica è ambigua se esiste anche solo una stringa che ha più di un albero sintattico, se tutte le sue stringhe hanno solo un albero sintattico allora la grammatica è non ambigua.

A volte si può rimuovere l'ambiguità, ma non sempre, e non esistono algoritmi sistematici per rimuoverla, alcuni linguaggi sono per forza ambigui, togliere l'ambiguità è indecidibile. Con le proprietà di chiusura dei CFL discutiamo le operazioni che sono interne, ovvero: unione, concatenazione, chiusura di Kleene e chiusura positiva. Non sono chiusi rispetto all'intersezione perché non si riesce a fare una simulazione parallela, servirebbero due pile ma allora si andrebbe alla versione di Touring, una dimostrazione è che a volte facendo l'intersezione si esce dai liberi. Se ho un libero e un regolare invece è possibile fare un'intersezione visto che in solo uno dei due uso la pila allora il risultato avrà una pila sola e sarà un libero quindi va bene.

Decidibilità

Decidibile significa avere un algoritmo, indecidibile significa che non esiste. Sono decidibili:

• Da grammatica CFG a PDA e viceversa nelle due direzioni.
• Da grammatica CFG a forma di Chomsky CNF.
• Data una grammatica o una qualsiasi forma capire se c'è almeno una stringa (che il linguaggio sia vuoto).
• Data una stringa e una grammatica capire se la stringa è generata da essa (problema del parsing), senza questa regola non esisterebbero i compilatori.

Sono indecidibili:

• Data una grammatica se è ambigua.
• Capire se c'è modo di disambiguare una grammatica.
• Capire se l'intersezione di due grammatiche CFL è vuota.
• Il problema di equivalenza dei liberi (se riconoscono lo stesso linguaggio), a differenza dei regolari che è decidibile.
• Se una grammatica CFL è universale, ovvero se riconosce tutte le stringhe.

Automi a pila (PDA)

Un automa a pila eredita il non determinismo e quindi è in pratica un epsilon-NFA con una pila. Un automa a pila si abbrevia in inglese in PDA (push down automaton). Come gli altri NFA dopo aver "mangiato" tutta la stringa ed aver percorso tutti i cammini risponde con un accept/reject, ora le transizioni oltre che dire "mangia" questo simbolo oppure epsilon dice cosa fare anche con lo stack (si arricchiscono le transizioni).

Ho 3 stati, q0 lo stato dove metto le cose sulla pila, q1 dove le tolgo confrontandole con l'input e q2 lo stato dove accetto se ho svuotato la pila. Z0 è l'elemento con cui parte lo stack. Di com'è messa la pila (stack) alla fine non mi interessa niente, insomma se alla fine dopo aver scorso tutta la stringa sono in uno stato di accettazione allora la stringa è accettata. I controlli sono solo sul top della pila. Un automa a pila è una tupla a 7 elementi. Gli automi con accettazione a stati finali.