Che materia stai cercando?

Anteprima

ESTRATTO DOCUMENTO

Gli AUTOMI A PILA (PDA, PUSHDOWN AUTOMATA) sono caratterizzati dalla presenza

di una memoria organizzata a stack. Il funzionamento della pila lo sai benissimo qual è.

Indicheremo con Z il marcatore di fondo della pila. Sono essenzialmente come gli FSA a

0

cui però aggiungiamo una memoria interna. L'automa quindi decide non solo in base

all'ingresso e allo stato attuale, ma anche in base al contenuto della pila. In particolare in

base all'elemento visibile della pila, cioè quello che sta in cima.

L'ACCETTAZIONE di una stringa avviene se, una volta completata la lettura della stringa,

l'automa si trova in uno stato finale. Specifichiamo chiaramente che la stringa deve essere

processata tutta. Vale anche negli FSA, ma qui lo esplicitiamo perché più avanti non sarà

necessariamente così. Mettiamolo subito in pratica questo automa e mostriamo che è in

n n

grado di leggere il linguaggio a b , che non era leggibile dagli FSA.

La notazione sulle transizioni è input, valore in cima / valore da inserire (in sostituzione del

precedente). Si usa la stringa ε per indicare la cancellazione dell'elemento in cima.

Definiamo un automa a pila come una tupla <Q, I, Γ, δ, q , Z , F> dove:

0 0

Q è un insieme finito di stati

– I è l'alfabeto di ingresso

– Γ è l'alfabeto dello stack

– δ è la funzione di transizione

– ∈

q Q è lo stato iniziale

– 0 ∈

Z Γ è il delimitatore di fondo pila

– 0

F Q è l'insieme di stati finali

La funzione di transizione per gli automi a pila è una funzione Q × (I∪{ε}) × Γ→ Q × Γ* ed

è definita come δ(q, i, A) = <p, α> ovvero prende come ingressi lo stato attuale, l'input e la

cima dello stack e ritorna uno stato finale e una nuova cima dello stack. È importante dire

che nei PDA la funzione di transizione è sempre una funzione PARZIALE. Nei PDA è

infatti possibile definire δ(q, ε, A) ovvero una transizione senza ingresso. Questi casi

particolari sono chiamati EPSILON MOSSE o MOSSE SPONTANEE, perché avvengono

in determinate condizioni senza ingressi particolari. Queste mosse ci obbligano a

conoscere tutto l'ingresso sin dall'inizio.

La CONFIGURAZIONE è una generalizzazione del concetto di stato. Si tratta infatti una

tupla c <q, x, γ> con:

q Q lo stato attuale

– ∈

x I* la stringa ancora da processare

– ∈

γ Γ* il contenuto dello stack

– ⊢

Il passaggio da una configurazione all'altra si chiama TRANSIZIONE ( ) ed è definito

proprio dalla funzione di transizione. Essa può essere causata dall'input della stringa

oppure da una mossa ε. Vediamo formalmente la differenza.

MOSSA STANDARD MOSSA Ε

δ(q, i, A) = <q’, α> δ(q, ε, A) = <q’, α>

⊢ ⊢

c = <q, x, γ> c’ = <q’, x’, γ’> c = <q, x, γ> c’ = <q’, x’, γ’>

γ = Aβ γ = Aβ

x = iy

→ γ’ = αβ → γ' = αβ

→ x' = y → x' = x

⊥ ∀ ∈ ⊥

Una proprietà importantissima è che se δ(q, ε, A) ≠ allora i I δ(q, i, A) = ovvero

la funzione di transizione è parziale! Questo deve verificarsi perché altrimenti il

comportamento dell'automa nella configurazione (q, A) non sarebbe prevedibile (problema

del non determinismo).

Definiamo la CONDIZIONE DI ACCETTAZIONE che una stringa viene accettata se

esistono una o più transizioni che portano dallo stato iniziale allo stato finale.

∀ ∈ ∈ ⇔ ⊢ ∈

x I* (x L c = <q , x, Z > * c = <q, ε, γ> q F)

0 0 0 F

Sappiamo che i PDA hanno un maggiore potere espressivo degli FSA. Permettono di

leggere tutti i linguaggi regolari, ma anche linguaggi in cui è richiesto contare per un

numero indefinito di volte. Un altro esempio di linguaggio che non può essere interpretato

R R

da un FSA è L = {wcw } dove indica la riflessione della stringa. Le mosse ε generano

però un difettuccio in questi automi: possono esserci delle transizioni che non arrivano mai

ad uno stato finale e si looppano! Questi loop non aggiungono nessun potere espressivo

ai PDA (cioè non ci sono linguaggi che possono essere accettati grazie a questi loop). È

buona idea quindi cercare di liberarcene. La notazione <q,x,α> * <q’,y,β> significa che

d

⊢ ⊥ ⊢

<q,x,α> * <q’,y,β> e, per β = Zβ’, hai che δ(q’, ε, Z) = . Ovvero il simbolo * d

rappresenta una sequenza di mosse che ha bisogno di un simbolo per procedere. A

∀ ∈ ∃ ∃

questo punto possiamo dire che un PDA è libero da loop se e solo se x I* q γ <q ,

0

x, Z > * <q, ε, γ> è in grado di arrivare al termine leggendo l'intera stringa, ovvero non

0 d

looppa per mezzo di mosse ε. Qualsiasi PDA può essere trasformato in un equivalente

libero da loop.

I linguaggi comprensibili ai PDA sono chiusi solo rispetto al complemento (che non è facile

individuare). Non sono chiusi invece nell'unione, nell'intersezione e nella differenza. Per

n n n 2n

esempio i linguaggi {a b } e {a b } sono interpretabili da singoli PDA, ma non esiste

nessun PDA che interpreta l'unione di quei due linguaggi.

Anche per i PDA esistono dei trasduttori che hanno un nastro di uscita. Non sto qui a

formalizzare perché è una PALLA pazzesca...

La LOGICA DELLE PREPOSIZIONI è basata su un linguaggio L che dispone di:

Un ALFABETO finito di simboli numerabili

– ∧ ∨

CONNETTIVI LOGICI ¬ → ↔

– SEGNI DI PUNTEGGIATURA ( )

Un SET DI FORMULE è definito ricorsivamente come:

Ogni proposizione (simbolo dell'alfabeto) è una formula

– ∧ ∨

Se F e G sono formule, allora tutte le combinazioni ¬F, F G

, F G , F → G, F ↔ G

– sono formule ∧ ∨

La precedenza degli operatori è ¬ → ↔

Se A è una proposizione, A e ¬A sono chiamati LETTERALI.

A è chiamato LETTERALE POSITIVO. ¬A è chiamato LETTERALE NEGATIVO.

Se L è un letterale, ¬L è il suo COMPLEMENTARE.

Nella logica delle proposizioni, ad ogni formula si associa un valore di verità tra VERO e

FALSO. L'INTERPRETAZIONE I è una funzione che assegna ad ogni proposizione un

valore di verità. Il simbolo I |= F indica che I rende vero F.

Tavole di verità dei connettivi logici: ∧ ∨

F G ¬F F G F G F → G F ↔ G

vero vero falso vero vero vero vero

vero falso falso falso vero falso falso

falso vero vero falso vero vero falso

falso falso vero falso falso vero vero

Se I |= F allora si dice che I è un MODELLO.

F è una TAUTOLOGIA se per ogni interpretazione I vale che I |= F.

F è SODDISFACIBILE se esiste almeno un'interpretazione I tale che I |= F.

F è FALSIFICABILE se esiste almeno un'interpretazione I tale che I |≠ F.

F è una CONTRADDIZIONE se per ogni interpretazione I vale che I |≠ F.

F è CONTINGENTE se è sia soddisfacibile che falsificabile.

Un insieme di formule F COMPORTA LOGICAMENTE un insieme di formule G quando

tutti i modelli di F sono anche modelli di G. La conseguenza logica si verifica con le mitiche

tabelle di verità che però hanno complessità esponenziale.

Due formule F e G sono EQUIVALENTI se vale F |= G e anche G |= F. Lo sono tute quelle

proprietà che conosciamo dell'algebra booleana:

F F ≡ F

F F ≡ F

∧ ∧

F G ≡ G F

∨ ∨

F G ≡ G F

∧ ∧ ∧ ∧

F (G H) ≡ (F G) H

∨ ∨ ∨ ∨

F (G H) ≡ (F G) H

∧ ∨

(F G) F ≡ F

∨ ∧

(F G) F ≡ F

∧ ∨ ∧ ∨ ∧

F (G H) ≡ (F G) (F H)

∨ ∧ ∨ ∧ ∨

F (G H) ≡ (F G) (F H)

¬¬F ≡ F

∧ ∨

¬(F G) ≡ ¬F ¬G

∨ ∧

¬(F G) ≡ ¬F ¬G

F ↔ G ≡ (F → G) (G → F)

F → G ≡ ¬F G

F → G ≡ ¬G → ¬F

Le equivalenze si studiano sostanzialmente per riscrivere pezzi di formula in modo più

semplice. Se abbiamo due formule equivalenti possiamo sostituire una formula all'interno

di un'altra senza cambiare la tabella di verità. Inoltre per ottenere una certa tabella di

verità non è per forza necessario avere a disposizione tutti i connettivi logici. L'insieme

{not, and} è FUNZIONALMENTE COMPLETO perché può simulare il comportamento di

tutti gli altri connettivi. Anche gli operatori logici {nand} e {nor} formano da soli un insieme

funzionalmente completo.

Ogni formula può essere indicata in FORMA NORMALE CONGIUNTIVA o FORMA

NORMALE DISGIUNTIVA. Equivalgono esattamente alle forme canoniche somma di

prodotti e prodotto di somme che abbiamo visto in ACSO.

Noi sappiamo che si può passare da una forma logica ad un'altra equivalente. È possibile

effettuare questo passaggio computazionalmente? I CALCULI sono un insieme di assiomi

e regole di inferenza che permettono questo passaggio. Questi elementi forniscono una

relazione di derivabilità tra due formule. Diciamo che F |-- G se è possibile passare da F a

G usando solo questi assiomi e regole di inferenza. Idealmente la relazione di derivabilità

dovrebbe essere SOUND (ovvero se F |-- G allora F |= G) e COMPLETA (ovvero se F |=

G allora F |-- G).

La logica delle proposizioni ha tante applicazioni, ma la sua potenza espressiva è limitata.

È qui che arriva in soccorso la LOGICA DEL PRIM'ORDINE o LOGICA DEI PREDICATI

che è una sua estensione. Questa logica infatti si estende considerando OGGETTI,

PROPRIETÀ/RELAZIONI e FUNZIONI.

L'alfabeto della logica del prim'ordine è composta da:

Un set infinito e numerabile di variabili X, Y, Z...

– Un set di simboli di funzioni f, g...

– Un set di simboli di relazioni p, q, r...

– ∧ ∨

I connettivi logici ¬ → ↔

– ∃ ∀

I quantificatori

– I simboli di punteggiatura ( ) ,

Ogni funzione e simbolo di relazione ha una sua ARIETÀ, cioè il numero di argomenti che

richiede. La scritta p/n dice che il simbolo p richiede n argomenti. Le funzioni con zero

argomenti si chiamano COSTANTI. I predicati con zero argomenti si chiamano

PROPOSIZIONI. Quindi la logica delle proposizioni aveva predicati senza argomenti.

Gli argomenti delle funzioni sono detti TERMINI. I termini sono definiti ricorsivamente

come una singola variabile oppure, se ho una funzione n-aria f/n e l'insieme t , t ...t è

1 2 n

composto da termini, allora anche f(t , t ...t ) è un termine. Quest'ultimo viene chiamato

1 2 n

anche FORMULA ATOMICA. Le altre formule sono applicazioni dei connettivi logici e dei

quantificatori agli atomi.

Nella traduzione di frasi in logica dei predicati bisogna considerare due cose:

Il quantificatore è usato insieme a →

– ∃ ∧

Il quantificatore è usato insieme a

Nella lezione sugli automi a pila abbiamo visto che ci sono linguaggi che non possono

riconoscere, perché la famiglia di linguaggi riconosciuti non è chiusa rispetto all'unione. Un

n n n n n n 2n

PDA non può per esempio interpretare i linguaggi a b c e a b unione a b . Questo

perché lo stack è una memoria distruttiva: quando un dato viene letto viene anche

rimosso. È necessaria una macchina con memoria persistente, ciò che è la MACCHINA DI

TURING. È il primo modello più vicino ai computer attuali, e dispone di una memoria

permanente che può essere letta più volte in qualsiasi momento, in qualsiasi direzione.

Le macchine di Turing sono composte in modo simile agli automi precedenti: hanno un

nastro di ingresso, eventualmente uno di uscita e uno o più nastri di memoria con un

numero di celle idealmente infinito, dove indichiamo con un apposito simbolo, per esempio

␢, che sono vuote. Le mosse di una macchina di Turing sono composte da un simbolo

letto in ingresso, da un numero K di simboli (uno per ogni nastro di memoria) e dallo stato

attuale. Le azioni che si possono fare sono cambiare stato, sovrascrivere i K simboli sui

nastri di memoria e spostare la testina su di essi. Lo spostamento può avvenire in tre

modi: a sinistra (L), a destra (R) o stare fermi (S). Il tipo di spostamento va indicato

esplicitamente e si può fare anche sul nastro di ingresso! Sulle transizioni quindi si

scriverà i, <A , A ..A > / <A ', A '...A '>, <M , M , M ...M > dove i è il simbolo in ingresso,

1 2. n 1 2 n 0 1 2 n

A è il simbolo presente sul k-esimo nastro, A ' è il simbolo da rimpiazzare sul k-esimo

k k

nastro mentre M è lo spostamento da fare sul k-esimo nastro. M è lo spostamento sul

k 0

nastro di ingresso. È da far notare che, mentre i PDA possono scrivere più simboli sullo

stack, le macchine di Turing possono scrivere solo un carattere alla volta sui nastri di

memoria.

Le formalizzazioni se non strettamente necessarie non le facciamo perché mi hanno rotto.

Sulle macchine di Turing bisogna precisare due cose: non esistono le epsilon mosse e

la lettura delle stringhe termina non appena si raggiunge uno stato finale! Quindi

bisogna fare attenzione a questi aspetti per mettere gli stati giusti... e si può arrivare in uno

stato finale senza che la macchina abbia letto tutta la stringa! Ecco l'esempio di una

n n n

Macchina di Turing che legge il linguaggio a b c :

I linguaggi interpretati da una macchina di Turing ovviamente comprendono anche quelli

dei PDA (basta usare la memoria come se fosse uno stack) e si chiamano ENUMERABILI

RICORSIVAMENTE.

Le macchine di Turing sono formalmente uguali a quelle di Von Neumann, che

rappresentano i computer attuali. La differenza sta nell'accesso alla memoria che per

Turing è sequenziale mentre per Von Neumann è ad accesso casuale. Questo rende la

macchina di Von Neumann più veloce ma ha lo stesso potere espressivo.

I linguaggi delle macchine di Turing sono chiusi rispetto a intersezione, unione,

concatenazione, stella di Kleeni ma NON rispetto al complemento e alla differenza!

Questo avviene principalmente perché le macchine di Turing hanno il problema di poter

non terminare mai la lettura e di finire in loop eterno (proprio come i nostri computer lelz).

Facendo il complemento di un linguaggio potremmo ottenerne uno che ha questi loop e

che non portano alla condizione di accettazione richiesta per il complemento.

Anche le macchine di Turing ovviamente possono avere un nastro di uscita e comportarsi

come traduttori (in cui però il nastro di uscita può solo muoversi a destra e star fermo, non

muoversi a sinistra), e come detto prima hanno la stessa espressività di una macchina di

Von Neumann, in quanto l'unica differenza è il tipo di accesso alla memoria. È una

macchina che concettualmente è molto semplice, ma progettarle non lo è altrettanto. Si

vede benissimo nell'esempio in cui bisogna semplicemente incrementare un numero di 1 :)

Esistono centinaia di varianti della macchina di Turing, ma tutte quante hanno lo stesso

potere espressivo. Esiste persino una variante detta A NASTRO SINGOLO in cui si usa

un solo nastro come input, memoria e uscita! E nonostante ciò riesce a esprimere tutti i

linguaggi che sanno codificare le altre macchine di Turing (ovviamente richiede un numero

enorme di passi ma ce la fa). In queste macchine l'unico nastro viene considerato illimitato

da entrambi i lati, dato che invece negli altri modelli i nastri erano infiniti da un lato ma

avevano un punto di partenza ben definito.

Altre varianti hanno per esempio dei nastri a matrice, per cui i movimenti non sono solo in

due direzioni ma ben otto, perché puoi andare sopra, sotto, a destra, a sinistra e negli

angoli. Nonostante tuta questa varietà, si può dimostrare (per fortuna non lo facciamo) che

tutti questi modelli sono tra loro equivalenti dal punto di vista espressivo. Ciò che cambia

naturalmente è l'efficienza (una macchina di Turing a nastro singolo richiede numerosi stati

e transizioni in più rispetto a una tradizionale).

Tutti i modelli visti finora sono DETERMINISTICI, ovvero ad ogni input esiste una ed una

sola transizione ben definita. Ci sono dei casi però in cui ad un certo input non sappiamo

quale sia la strada giusta per arrivare alla soluzione, e dobbiamo quindi “scegliere” una

strada. Per esempio, se dobbiamo fare una macchina di Turing che riconosca se un

numero è divisibile per 4 leggendo le cifre da sinistra, ci serve sapere quali sono le ultime

due cifre del numero. Ma mentre leggiamo le cifre non possiamo sapere se quella che

stiamo ricevendo è già la penultima, l'ultima o una nel mezzo, quindi ci tocca “indovinare”

in quale situazione ci troviamo. Questa situazione si chiama NON DETERMINISMO e

graficamente si rappresenta con delle transizioni a diversi stati con lo stesso input. Nella

pratica è come se avessimo più thread che prendono strade diverse.

La funzione di transizione δ nelle macchine non deterministiche non è più una funzione nel

senso tradizionale del termine, perché non porta da un input ad uno stato ben preciso, ma

porta ad un insieme di stati possibili, chiamato INSIEME DELLE PARTI. Nella funzione δ*

che, dato un input ritorna tutto il percorso, lo stato d'arrivo diventa l'unione di tutti gli stati

d'arrivo. La CONDIZIONE DI ACCETTAZIONE è che almeno uno dei percorsi possibili

porti ad uno stato di accettazione.

Ci chiediamo qual è la differenza espressiva tra gli automi deterministici e quelli non,

iniziando dagli automi a stati finiti. Beh, tra un DFSA e un NDFSA non cambia proprio

nulla! Dato un automa a stati finiti non deterministico possiamo tradurlo in una versione

deterministica. Per farlo basta raggruppare gli stati d'arrivo in un unico statone e definiamo

le transizioni per questo statone. Se nell'insieme di arrivo c'è uno stato d'arrivo, anche lo

statone sarà uno stato d'arrivo. Il problema è che questo lavoro, oltre a essere noioso da

mandarti ai pazzi, rende l'automa deterministico con una quantità di stati enorme, con un

aumento esponenziale nel caso peggiore. Per questo gli automi non deterministici

diventano anche più facili da progettare e realizzare.

Vediamo ora cosa succede nelle macchine di Turing: la computazione può essere

espressa tramite un albero che può terminare in stato di accettazione, terminare senza

accettare oppure non terminare mai. Per questo motivo non possiamo esplorare l'albero

per profondità, perché se finiamo in un ramo infinito non torniamo più su. L'idea migliore è

esaminarlo per livelli, così, se c'è una condizione di accettazione, la raggiungiamo

sicuramente. Una macchina di Turing non deterministica quindi equivale ad esplorare un

albero di computazione per livelli. Anche per questi automi però il non determinismo non

aggiunge alcun potere espressivo, quindi possiamo tradurre un automa non deterministico

in uno deterministico. Non abbiamo visto come perché è ancora più noioso e lungo

rispetto agli FSA, però è bene sapere questa proprietà.

Ora è il turno degli automi a pila e qui succede qualcosa di interessante. Quando li

abbiamo studiati abbiamo detto che, se è definita una transizione su una mossa epsilon,

non possono essere definite transizioni per altri simboli, altrimenti l'automa non sarebbe

più stato deterministico. Un automa a pila diventa non deterministico semplicemente

togliendo questo vincolo. La magia qui però è che il non determinismo aggiunge

espressività agli automi a pila! Quelli tradizionali non potevano riconoscere l'unione dei

n n n 2n

linguaggi a b e a b . Con il non determinismo invece possiamo riconoscerlo!

Otteniamo una nuova classe di linguaggi riconoscibili dagli NDPDA che si chiama

CONTEXT FREE. Per chiarirci le idee, gli insiemi di linguaggi visti finora, dal più piccolo al

più esteso, sono:

LINGUAGGI REGOLARI (DFSA e NDFSA)

– LINGUAGGI CONTEXT-FREE DETERMINISTICI (DPDA)

– LINGUAGGI CONTEXT-FREE NON DETERMINISTICI (NDPDA)

– LINGUAGGI ENUMERABILI RICORSIVAMENTE (DTM NDTM)

Questa nuova classe di linguaggi è chiusa rispetto all'unione (i PDA tradizionali non lo

erano) perché permette il trucchetto delle due biforcazioni con una mossa epsilon. Non è

comunque chiusa nel complemento e intersezione. Il complemento si può fare solo nelle

macchine deterministiche e che garantiscono il termine della computazione. In questi casi

allora si può completare la macchina e swappare gli stati finali con quelli non finali.

Finora abbiamo visto gli automi, che sono modelli operazionali dei linguaggi, ovvero data

una stringa la elaborano, eventualmente la traducono e dicono se appartiene ad un

linguaggio. Le GRAMMATICHE invece sono dei modelli generativi, cioè forniscono delle

regole per generare le stringhe di un linguaggio, di qualsiasi tipo (naturale, di

programmazione, logico ecc...). Ciò viene fatto attraverso un processo di RISCRITTURA

che può essere anche non deterministico.

Ogni linguaggio è descritto da elementi minimi che fanno parte di elementi via via più

grandi. Per esempio in un linguaggio naturale abbiamo:

Una frase è composta da un soggetto e da un predicato

– Un soggetto può essere un nome, un pronome o...

– Un predicato può essere un verbo seguito da un complemento

O per un linguaggio di programmazione le regole possono essere:

Un programma consiste di una parte dichiarativa e una parte esecutiva

– La parte dichiarativa...

– La parte esecutiva consiste in una serie di istruzioni

– Una istruzione è...

In generale, le regole linguistiche descrivono un OGGETTO PRINCIPALE come

sequenza di OGGETTI COMPOSTI. Ogni oggetto composto viene sostituito via via da

oggetti più piccoli e dettagliati, fino ad arrivare ad una serie di OGGETTI ELEMENTARI.

Le grammatiche sono regole linguistiche composte da:

Un oggetto principale: SIMBOLO INIZIALE

– Oggetti composti: SIMBOLI NON TERMINALI

– Oggetti elementari: SIMBOLI TERMINALI

– Regole di trasformazione: PRODUZIONI

– <V , V , P, S>

Formalmente una grammatica si può definire come una tupla dove:

N T

V è l'alfabeto non terminale

– N

V è l'alfabeto terminale

– T

S è un elemento di V chiamato simbolo iniziale

– N

P è l'insieme di produzioni

Le produzioni sono regole che spiegano come trasformare i simboli nella forma α → β

dove α è una stringa contenente almeno un carattere non terminale e β una stringa

(potenzialmente vuota) contenente simboli terminali o non. D'ora in poi indicheremo i

simboli non terminali con lettere maiuscole e i simboli terminali con lettere minuscole. Una

stringa apparterrà al linguaggio se sarà composta dai soli simboli terminali. Vediamo un

esempio:

V = {S, A, B, C, D}

N

V = {a, b, c}

T

Il simbolo iniziale è S

P = { S → AB,

BA → cCD,

CBS → ab,

A → ε

}

Ma sto linguaggio non genera nulla ._.

Chomsky ha catalogato i linguaggi in quattro categorie in base alla loro espressività e alle

regole di produzione. Sono classificati come linguaggi di TIPO 0, TIPO 1, TIPO 2, TIPO 3

dove il più espressivo è il tipo 0 mentre il meno espressivo è il tipo 3. Vedremo fra

pochissimo che c'è una corrispondenza tra questi linguaggi e quelli riconosciuti dagli

automi che abbiamo studiato finora.

LINGUAGGI DI TIPO 3

Sono i linguaggi più semplici. Le produzioni hanno a sinistra un solo carattere non

terminale. A destra possono avere un singolo non terminale, un terminale + un non

terminale oppure la stringa vuota. Un'altra variante ammette la sequenza non terminale +

terminale (cioè ordine scambiato) ma non possono coesistere entrambe le forme nello

stesso linguaggio.

X → y

X → yY oppure X → Yy (ma non entrambi)

X → ε (vale solo se X non appare a destra in nessun'altra produzione)

LINGUAGGI DI TIPO 2

Hanno a sinistra un solo non terminale (come nel tipo 3), mentre a destra può esserci

qualsiasi cosa vogliamo.

X → vuGVYFVgfJFTYGv

LINGUAGGI DI TIPO 1

I linguaggi di tipo 1 hanno produzioni nella forma αAβ → αγβ dove A è un non terminale, α

e β possono essere qualsiasi cosa (li chiamiamo CONTESTO) e γ è non vuoto. X → ε vale

solo se X non appare a destra in nessun'altra produzione. Se il contesto è vuoto ci

riconduciamo ai linguaggi di tipo 2.

LINGUAGGI DI TIPO 0

Non hanno regole, fanno tutto.

Si ha una DERIVAZIONE IMMEDIATA se da una stringa alfa contenente almneo un

terminale, passiamo ad una stringa beta in cui il non terminale viene sostituito con

qualcos'altro (i non terminali da soli non si possono sostituire). In certe grammatiche può

succedere che in alcuni casi la sostituzione possibile non è unica e ce ne sono tante altre

possibili, ovvero abbiamo del NON DETERMINISMO. Alcune scelte arrivano a produrre

stringhe del linguaggio con soli terminali, altre no.

Il linguaggio generato da una grammatica è il linguaggio che contiene tutte le

stringhe di sole terminali per cui esiste una sequenza di derivazioni immediate che,

a partire dal simbolo iniziale, arrivano alla stringa esaminata. Deve esserci almeno

una derivazione perché il simbolo di partenza S è non terminale. Il non determinismo è

praticamente obbligatorio perché ogni stringa deve poter essere generata dal simbolo

iniziale S.

Esempio con G = <{S, A, B}, {a, b, 0}, S, P>

P = { S → aA | bB | 0,

A → aS,

B → bS

}

È una grammatica di tipo 3. Facciamo alcune derivazioni:

S → 0

S → aA → aaS → aaaA → aaaaS → aaaa0

S → bB → bbS → bbaA → bbaaS → bbaa0

In generale sono tutte le stringhe nella forma {aa, bb}*.0

Facendo altri esempi viene subito fuori che c'è una relazione tra i linguaggi generati dalle

grammatiche, le gerarchie di Chomsky e i linguaggi compresi dagli automi. Possiamo

rinominare ogni classe di linguaggi in questo modo:

Tipo 3 → GRAMMATICHE REGOLARI, generano i linguaggi regolari compresi

– dagli automi a stati finiti;

Tipo 2 → GRAMMATICHE NON CONTESTUALI, generano i linguaggi context-free

– compresi dagli automi a pila non deterministici;

Tipo 1 → GRAMMATICHE DIPENDENTI DAL CONTESTO, generano una

– particolare classe di linguaggi che sono comprensibili da un tipo di automa che non

abbiamo studiato, per cui non li faremo mai;

Tipo 0 → GRAMMATICHE NON RISTRETTE o GENERALI, generano i linguaggi

– enumerabili ricorsivamente, riconosciuti dalle macchine di Turing

Gerarchia di Grammatiche Linguaggi Automi

Chomsky

Tipo 0 Non ristrette Ricorsivamente enumerabili Macchine di Turing

Tipo 1 Dipendenti dal contesto Dipendenti dal contesto ---

Tipo 2 Libere dal contesto Context-free Automi a pila non

deterministici

Tipo 3 Regolari Regolari Automi a stati finiti

Le grammatiche regolari, gli automi a stati finiti e le espressioni regolari sono diversi

modelli per descrivere la stessa classe di linguaggi. Per passare da una grammatica

regolare ad un automa a stati finiti (e viceversa) basta porre una corrispondenza:

Stati non finali q = Simboli non terminali S

– i i

Simboli di input I = Simboli terminali V

– T

Stati finali q = S → ε

– F i

Stato iniziale q = Simbolo S

– 0

Transizioni δ(q, i) = q' diventano S → iS'

Le grammatiche context-free sono alla base del formalismo dei linguaggi di

programmazione e dei linguaggi naturali, anche dei compilatori!

Poi spiega anche come passare da una grammatica non ristretta alla corrispettiva

macchina di Turing ma non is capisce niente...


ACQUISTATO

1 volte

PAGINE

28

PESO

816.41 KB

AUTORE

fiorixf2

PUBBLICATO

+1 anno fa


DETTAGLI
Corso di laurea: Corso di laurea in ingegneria informatica (COMO - CREMONA - MILANO)
SSD:
A.A.: 2017-2018

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher fiorixf2 di informazioni apprese con la frequenza delle lezioni di Principi dell'informatica e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università Politecnico di Milano - Polimi o del prof Martinenghi Davide.

Acquista con carta o conto PayPal

Scarica il file tutte le volte che vuoi

Paga con un conto PayPal per usufruire della garanzia Soddisfatto o rimborsato

Recensioni
Ti è piaciuto questo appunto? Valutalo!

Altri appunti di Corso di laurea in ingegneria informatica (como - cremona - milano)

Guida per la programmazione in C
Dispensa
Esercizi sulla programmazione in C
Esercitazione
Architettura dei calcolatori e sistemi operativi - Appunti
Appunto
Livello di linea
Appunto