Linguaggi Formali e Compilazione: Automi

LFC

Automi diriconoscimentoAutomi a stati finiti

Automi a pila (pushdown)

Linguaggi formali e compilazioneCorso di Laurea in Informatica

A.A. 2008/2009

LFC



Linguaggi formali e compilazione

Automi di riconoscimentoAutomi a stati finitiAutomi a pila

LFC



Obiettivo di questa parte del corso

◮ Descriveremo gli automi a stati finiti e gli automi apila, che sono importanti strumenti modellistici chetrovano amplissima applicazione (in particolare gliautomi finiti) in molti settori dell’Informatica.

◮ Vedremo come gli automi finiti siano un formalismo“equivalente” alle espressioni regolari.

◮ Comprenderemo meglio il funzionamento distrumenti per la generazione automatica dianalizzatori lessicali (come Lex).

LFC



Definizione informale

◮ Un automa a stati finiti deterministico (ASFD), puòessere visto come un calcolatore elementare dotatodi stato interno e supporto unidirezionale di input.

◮ Il funzionamento dell’automa consiste di transizionidi stato a seguito della lettura di un simbolo da undispositivo di input.

◮ Ad ogni stato q sono in generale associate azioni(come la stampa di messaggi) che l’automa eseguequando transita in q.

◮ Gli ASFD sono ampiamente utilizzati in molti settoridell’Informatica, non solo nel contesto dei linguaggiformali.

LFC



Descrizione formale

Un ASFD M è una quintupla

M = (Σ, Q, q0, Qf , δ) ,

in cui

- Σ è l’alfabeto di input;

- Q è un insieme finito i cui elementi sonodetti stati dell’automa;

- q0 è un elemento speciale di Q, detto statoiniziale;

- Qf ⊆ Q è l’insieme degli stati finali, dettianche di accettazione dell’input;

- δ è la funzione che determina le transizionidi stato. Essa mappa coppie 〈stato, simbolo〉in stati: δ : Q × Σ→ Q.

LFC



Computazioni di un automa

◮ Definibili in modo intuitivo come sequenza di passi.◮ Ad ogni passo, l’automa si trova in uno stato q

(inizialmente q = q0), legge un simbolo x dall’input etransita nello stato δ(q, x).

◮ La computazione termina quando:mancanza di input non vi sono più simboli di input,

oppuretransizione non specificata in corrispondenza dello

stato attuale e del simbolo letto, lafunzione di transizione non èspecificata.

◮ Il numero di transizioni effettuate prima dellaterminazione è detto lunghezza della computazionee ne rappresenta una misura del costo.

LFC



Rappresentazione di automi

◮ Un utile formalismo (molto diffuso perché “intuitivo”)è quello dei diagrammi di transizione.

◮ Un diagramma di transizione è un grafo i cui nodi edarchi rappresentano, rispettivamente, stati etransizioni.

◮ Ogni arco è etichettato da un simbolo di input.◮ Lo stato iniziale viene evidenziato mediante una

freccia entrante (e non uscente da alcun altro nodo).◮ Gli stati finali sono indicati tramite doppia cerchiatura

oppura da una freccia uscente (e non entrante inalcun altro nodo).

LFC



Esempio introduttivo

Il lupo, la pecora e il cavolo

ulpc- lc-up ulc-p

c-ulp l-upc

upc-l ulp-c

p-ulcup-lc-ulpc

p

p

u

u

ll

c

c

pp

pp

c

c ll

u

u

p

p

Esempio tratto da Hopcroft, Ullman (1979)

LFC



Automi riconoscitori

◮ Un ASFD riconosce (o accetta) una stringa X ininput se la computazione determinata dai caratteri diX termina in uno stato di Qf per mancanza di input.

◮ Un ASFD M riconosce un linguaggio L se e solo seL coincide con l’insieme delle stringhe riconosciuteda M.

LFC



Esempi

◮ Il seguente ASFD M5 riconosce il linguaggioL5 = {anbm|n, m ≥ 0}

0 1b

a b

◮ Il seguente ASFD M3 riconosce il linguaggioL3 = {01k0|k ≥ 0}

0 1

2

30

1

0

0

1

LFC



Esempi

◮ Il seguente ASFD M2 riconosce il linguaggioL2 = {X ∈ B∗ : |X | = 2}

0 1 20

1

0

1

◮ Il seguente ASFD Mparity riconosce il cosiddettolinguaggio parità, ovvero l’insieme delle stringheX ∈ B∗ che contengono un numero pari di 1

0 11

1

0 0

LFC



Simulazione di automi deterministici

◮ La simulazione del comportamento di un ASFDM = (Σ, Q, q0, Qf , δ) è particolarmente semplice.

◮ L’algoritmo riceve in ingresso M e l’input X per M eproduce l’output che darebbe M su input X .

◮ L’algoritmo presentato nella diapositiva seguente siriferisce alla simulazione di un generico automariconoscitore.

◮ Nella descrizione dell’algoritmo (in pseudocodice) sisuppone che:

◮ l’input X sia terminato dal carattere $;◮ tale carattere non appartiene all’alfabeto Σ

dell’automa;◮ se, per una determinata coppia stato-simbolo, 〈q, x〉,

la funzione di transizione è indefinita, si poneδ(q, x) = ⊥.

LFC



Algorithm 1 Simulazione di un ASFD1: q ← q0

2: x ← nextchar(X )3: while (x 6= $) do4: if δ(q, x) 6= ⊥ then5: q ← δ(q, x)6: else7: reject8: x ← nextchar(X )9: if q ∈ Qf then

10: accept11: else12: reject

LFC



Simulazione di automi deterministici

◮ Si noti che l’algoritmo è un vero e proprio interprete,ancorché molto semplice.

◮ Infatti, esso prende in input un programma M(l’automa) e un input X per il programma, ed“esegue” M su input X .

◮ È facile convincersi del fatto che il costo dellasimulazione è lineare nella lunghezza dell’input (apatto che si possa considerare costante il costo divalutazione della funzione δ, che tipicamente vieneimplementata mediante una tabella).

LFC



Esercizi proposti◮ Per ciascuno dei seguenti linguaggi, si fornisca un

ASFD che riconosce il linguaggio.◮

{

X |X ∈ {0,1}∗ , X non contiene 0 adiacenti}

◮

{

X |X ∈ {0,1}∗ , ogni sottostringa di lunghezza 3 in Xcontiene almeno due 1}

◮

{

X |X ∈ {a,b,c}∗ , due qualsiasi caratteri adiacenti in Xsono fra loro differenti}

◮ Progettare un ASFD che riconosce il linguaggiodescritto dalla seguente definizione regolare:

NZD = 1|2|3|4|5|6|7|8|9

D = 0|NZD

PI = NZD D∗|0

OPS = −|+ |ǫ

M = OPS PI.D∗

EXP = E OPS PI

FLOAT = M|M E

LFC



Automi non deterministici

◮ Un automa a stati finiti si dice non deterministico(ASFND) se, in almeno uno stato q, la transizionenon è univocamente determinata dal simbolo diinput.

◮ In altri termini, dallo stato q e con lo stesso simbolodi input l’automa può transitare in più di uno statodiverso.

◮ Nella definizione formale cambia solo la “funzione” ditransizione, che, in un ASFND, mappa coppie〈stato,simbolo〉 in sottoinsiemi (anziché elementi) diQ.

◮ Un ASFND M riconosce una stringa X sse esisteuna sequenza di transizioni che, su input X portal’automa in uno stato finale con mancanza di input.

LFC



Esempio◮ Il seguente automa è non deterministico perché nello

stato 0 ci sono due transizioni etichettate con ilsimbolo 1. In altri termini, la funzione di transizionemappa la coppia 〈0,1〉 nell’insieme {0, 1}

0 11

0

1

◮ È facile vedere che l’automa può accettare la stringadi input solo se questa termina con 1. Inoltre, perogni tale stringa esiste una sequenza di mosse chetermina nello stato 1 con mancanza di input.L’automa riconosce quindi il linguaggio (0|1)∗1.

◮ Nello stato 0 l’automa deve deciderenondeterministicamente, su input 1, se questo èl’ultimo carattere di input.

LFC



ASFND con ǫ-transizioni

◮ Un’ulteriore sorgente di non determinismo ècostituita dalle cosiddette ǫ-transizioni, cioètransizioni che mappano elementi di Q × {ǫ} in Q.

◮ Se in un diagramma di transizione l’arco che collegadue nodi q ed r è etichettato da ǫ, allora l’automapuò passare da q ad r “senza consumare input”.

◮ Il seguente ASFND include diverse ǫ-transizioni.

0

1

2

3

4

5

6

7

8ǫ a

a

ǫ

a

b

ǫ

ǫǫ

b

a

b

ǫ

LFC



Equivalenza di ASFD e ASFND

◮ Un risultato fondamentale è che, nel contesto degliautomi finiti, il non determinismo non amplial’insieme dei linguaggi riconoscibili.

◮ Ciò significa che un linguaggio L è riconoscibile daun ASFND se e solo se esiste un ASFD chericonosce L.

◮ La sufficienza della condizione è banale, visto che gliautomi deterministici sono un caso particolare diquelli non deterministici.

◮ La necessarietà della condizione si dimostramediante un processo noto come subsetconstruction: dato un ASFND N si costruisceesplicitamente un ASFD D che riconosce lo stessolinguaggio riconosciuto da N .

LFC



La cosiddetta “subset construction”

◮ Sia N = (Σ, Q, q0, Qf , δ) un dato ASFND.◮ Indicheremo con D = (Σ, DS, DQ0, DQf , DT )

l’automa equivalente, e la costruzione che seguemostra come sono definiti le componenti di D (aparte Σ).

◮ Osserviamo innanzitutto come DS ⊆ 2Q, in quantol’idea della simulazione è di tenere traccia (con glistati di D) dell’insieme di stati in cui si può trovare Ndopo aver letto un certa sequenza di input α.

◮ La costruzione procede (idealmente) in modoinduttivo sulla lunghezza di α.

LFC



La cosiddetta “subset construction” (continua)

◮ Supponiamo dapprima α = ǫ.◮ Senza consumare input, N si può trovare in q0 (lo

stato iniziale) come pure in uno qualsiasi degli statiraggiungibili da q0 mediante sole ǫ-transizioni.

◮ L’insieme di stati raggiungibili da uno stato assegnatoq mediante ǫ-transizioni (ai quali si include q stesso)viene indicato con ǫ-CLOSURE(q).

◮ Possiamo quindi dire che lo stato iniziale DQ0 di D èǫ-CLOSURE(q0).

LFC




◮ Per il passo induttivo si consideri uno statoQ′ = {q1, q2, . . . qk} di D, dove i qj sono gli stati in cuiN può trovarsi in seguito alla lettura di una certaporzione α dell’input.

◮ Leggendo un ulteriore simbolo x di input, N puòtransitare direttamente in uno qualunque degli stati diQ′′ = δ(q1, x) ∪ . . . ∪ δ(qk , x).

◮ Inoltre, senza consumare altro input, N potrebbemuoversi seguendo ǫ-transizioni.

◮ Ne consegue che, dopo aver letto la porzione di inputαx , N può trovarsi in uno qualunque degli stati inǫ-CLOSURE(Q′′).

◮ Tale stato viene quindi aggiunto a DS (se non giàpresente) e si pone anche

DT (Q′, x) = ǫ-CLOSURE(Q′′).

LFC




◮ Si noti che la ǫ-CLOSURE di un insieme Q di stati èdefinita in modo naturale come:

ǫ-CLOSURE(Q)=Q⋃

(

⋃

q∈Qǫ− CLOSURE(q)

)

.

◮ Il processo termina quando non si riesce più adaggiungere a D sottoinsiemi distinti di stati.

◮ Si noti che il processo termina sicuramente, perché ilnumero di sottoinsiemi distinti di stati di N è finito.

◮ Gli stati finali di D sono quelli che contengonoalmeno uno stato finale di N : si pone cioè

DQf = {DQ ∈ DS|∃q ∈ DQ t. c. q ∈ Qf}

LFC



Esempio di subset construction

◮ Consideriamo il seguente automa non deterministico,già introdotto a proposoto delle ǫ-transizioni:

0

1

2

3

4

5

6

7

8ǫ a

a

ǫ

a

b

ǫ

ǫǫ

b

a

b

ǫ

◮ Se indichiamo con A lo stato iniziale di D, avremoA = {0, 1, 8}.

◮ Si noti infatti che {0, 1, 8} = ǫ-CLOSURE(0).

LFC



Esempio di subset construction (continua)

0

1

2

3

4

5

6

7

8ǫ a

a

ǫ

a

b

ǫ

ǫǫ

b

a

b

ǫ

◮ Esaminiamo ora, a partire dagli stati di A, in qualistati si arriva su input a. Tali stati sono dapprima 2 e3 ma poi, considerando le ǫ-transizioni, anche gli stati4 e 8 (vale cioè ǫ-CLOSURE({2, 3})= {2, 3, 4, 8}).

◮ Poniamo quindi B = {2, 3, 4, 8} e δ(A,a) = B.

LFC




0

1

2

3

4

5

6

7

8ǫ a

a

ǫ

a

b

ǫ

ǫǫ

b

a

b

ǫ

◮ Poiché da A non si diparte alcuna transizioneetichettata b, passiamo a considerare le transizioniuscenti da B.

◮ Su input a, dallo stato 4 ∈ B si ritorna nello stato 2 equindi, mediante ǫ-transizioni, si può tornare in 4 e in8 (cioè ǫ-CLOSURE({2})= {2, 4, 8}).

◮ Poniamo quindi C = {2, 4, 8} e δ(B,a) = C.◮ Analogamente, considerando il carattere b di input,

avremo D = {5, 6, 7} e δ(B,b) = D.

LFC




0

1

2

3

4

5

6

7

8ǫ a

a

ǫ

a

b

ǫ

ǫǫ

b

a

b

ǫ

◮ Continuando in questo modo introduciamo dapprimala transizione δ(C,a) = C;

◮ quindi lo stato E = {8} e la transizione δ(D,a) = E ;◮ quindi lo stato F = {5, 6, 7, 8} e la transizione

δ(D,b) = F ;◮ quindi la transizione δ(F ,a) = E ;◮ infine la transizione δ(F ,b) = F .

LFC




◮ L’automa D risultante è:

A B

C

D E

F

a

a

bb

a

a

a b

dove

A = {0, 1, 8}

B = {2, 3, 4, 8}

C = {2, 4, 8}

D = {5, 6, 7}

E = {8}

F = {5, 6, 7, 8}

LFC



Implementazione della subset construction

◮ Dobbiamo dapprima decidere come rappresentare isottoinsiemi di Q, cioè gli elementi di DS,.

◮ Ad esempio, potremmo utilizzare bitmap di |Q|posizioni e rappresentare uno stato mediante unpuntatore alla opportuna bitmap.

◮ Ogni stato deve inoltre poter essere etichettato conun indicatore binario (diciamo bianco e nero).

◮ Dobbiamo quindi realizzare la struttura dati DS che“contiene” gli stati e una struttura dati (che sarà unatabella) che rappresenta la funzione di transizione diD,

◮ Per quanto riguarda DS, diciamo solo che essa deveprevedere operazioni di inserimento, ricerca edestrazione di stati bianchi.

◮ La diapositiva seguente illustra l’algoritmo.

LFC



Algorithm 2 Subset construction1: Inserisci ǫ-CLOSURE(q0) in DS e coloralo di bianco2: while esiste uno stato bianco S in DS do3: colora S di nero4: for all x ∈ Σ do5: T ← {}6: for all q ∈ S do7: T ← T ∪ δ(q, x)8: T ← ǫ-CLOSURE(T )9: if T 6∈ DS then

10: inserisci T in DS11: poni DT [S, x ] = T

LFC


Automi a pila (pushdown)Algorithm 3 Calcolo della ǫ-CLOSURE(T )1: for all q ∈ T do2: inserisci q su una pila3: Poni ǫ-CLOSURE(T )← T4: while La pila non è vuota do5: estrai q dalla pila6: if δ(q, ǫ) 6= ⊥ e δ(q, ǫ) = {q1, . . . , qk} then7: for i = 1, . . . , k do8: if qi 6∈ ǫ-CLOSURE(T ) then9: T ← {qi} ∪ ǫ-CLOSURE(T )

10: inserisci qi sulla pila

LFC



Generalità delle ǫ-transizioni

◮ Si può dimostrare che per ogni ASFND conǫ-transizioni esiste un ASFND senza ǫ-transizioniequivalente (cioè che riconosce lo stessolinguaggio).

◮ A noi interessa di più il fatto che le ǫ-transizionipossono essere l’unica sorgente di nondeterminismo senza che ciò comporti una perdita dicapacità di riconoscimento.

◮ Gli esempi che seguono mostrano l’idea alla basedella trasformazione di un ASFND (senzaǫ-transizioni) in un ASFND in cui l’unica sorgente peril non determinismo è costituita dalle ǫ-transizioni

LFC




◮ La porzione di automa

0

1

2

a

a

è equivalente a

0

1′

2′

1

2

ǫ

ǫ

a

a

LFC




◮ La porzione di automa

0

1

2

3

aaa

◮ è equivalente a

0

1′

2′

1

2′′

3′′

2

3

ǫ

ǫ

a

ǫ

ǫ

a

a

LFC



Esercizi proposti

◮ Si fornisca la grammatica lineare corrispondente alseguente automa

A B

C

D

a

b

b

ab

a

ba

◮ Si esibisca un automa non deterministico con soleǫ-transizioni equivalente all’automa dell’esercizioprecedente.

◮ Si fornisca un automa a stati finiti che riconosce illinguaggio denotato dalla seguente espressioneregolare:

(ba | b)∗ ba∗ (ab | b)

LFC



Automi finiti e grammatiche lineari

◮ Dato un automa a stati finiti M che riconosce illinguaggio L è immediato definire una grammaticalineare GM che genera lo stesso linguaggio, cioè taleche L(GM) = L.

◮ La costruzione è molto semplice:◮ per ogni stato q dell’automa la grammatica conterrà

un simbolo non terminale Aq ;◮ l’assioma iniziale è Aq0 ;◮ per ogni transizione δ(q,a) = q′, la grammatica

conterrà la produzione Aq → aAq′ ;◮ se q′ è uno stato finale, la grammatica conterrà la

produzione Aq → ǫ.

◮ La generalità della costruzione ci permette diconcludere che i linguaggi riconosciuti da automifiniti sono regolari (perchè avevamo vistoprecedentemente che grammatiche lineari edespressioni regolari sono formalismi equivalenti).

LFC



Automi finiti ed espressioni regolari

◮ Vedremo ora lo schema di costruzione, a partire dauna generica espressione regolare E , di un ASFNDche riconosce lo stesso linguaggio denotato da E .

◮ La generalità della costruzione ci consentirà diaffermare anche il viceversa di quanto visto poc’anzi,e cioè che tutti i linguaggi regolari sono riconoscibilida automi finiti (deterministici o non deterministici,con o senza ǫ-transizioni).

◮ Potremo quindi concludere che un linguaggio èregolare se e solo esiste un automa finito che loriconosce e che automi finiti, grammatiche lineari edespressioni regolari sono formalismi equivalenti.

LFC



Automi finiti ed espressioni regolari

◮ L’idea della costruzione è di “ripercorrere” ladefinizione ricorsiva delle epressioni regolari.

◮ Avremo automi elementari corrispondenti ai casibase della definizione delle espressioni regolari.

◮ Avremo poi regole di composizione degli automicorrispondenti alle regole di definizione diespressioni regolari per unione, concatenazione echiusura di altre espressioni regolari.

◮ Gli ASFND usati hanno ǫ-transizioni come unicasorgente di non determinismo.

◮ Più precisamente, gli stati dell’automa saranno didue soli tipi:

1. stati deterministici dai quali esce una sola transizioneetichettata con un simbolo di Σ;

2. stati non deterministici dai quali escono al più duetransizioni etichettate ǫ.

LFC



Costruzione dell’automa

◮ Il “caso base” consiste nel definire ASFD chericonoscono i singoli caratteri di Σ.

◮ Se a ∈ Σ avremo dunque l’automa base

0 21ε a

(NB In queste costruzioni utilizzeremo laconvenzione di individuare lo stato inizialeutilizzando il colore azzurro.)

◮ Nelle regole di composizione, gli automi utilizzatiavranno tutti la seguente forma standard, in cui siindividua: (1) uno stato iniziale dal quale escono alpiù due ǫ-transizioni; (2) uno stato finale, e (3) uncorpo dell’automa, composto da uno o più stati.

0ε

εfM

LFC



Costruzione dell’automa (continua)

◮ Dati due automi, M1 ed M2, che riconosconorispettivamente E1 ed E2, la seguente costruzionemostra l’automa M che riconosce E1E2.

0ε

εM2

0ε

εM1

ε

εM2

g

f g

0ε

εfM1

◮ L’automa viene costruito semplicemente“identificando” lo stato iniziale di M2 con lo statofinale di E1.

◮ Naturalmente è necessaria una ridefinizione deglistati (tipicamente di M2).

◮ Si noti inoltre come l’automa risultante verifichi leassunzioni soddisfatte da M1 ed M2.

LFC



Costruzione dell’automa (continua)◮ Dati due automi, M1 ed M2, che riconoscono

rispettivamente E1 ed E2, la seguente costruzionemostra l’automa M che riconosce E1 + E2.

ε

εfM1

ε

εM2 g

ε

ε

0

0’

0"

ε

0ε

εM2 g0

ε

εfM1

◮ L’automa viene costruito:1. inserendo un nuovo stato iniziale collegato (mediante

ǫ-transizioni) agli stati iniziali di M1 ed M2;2. facendo “puntare” uno dei due stati finali (scelto

arbitrariamente) all’altro mediante una ǫ-transizione.3. lasciando quest’ultimo come stato finale

complessivo.

LFC



Costruzione dell’automa (continua)

◮ Dato un automa M1 che riconosce E1, le seguenticostruzioni mostrano l’automa M che riconosce E∗.

0ε

g

εh

ε

ε

εM1 f0’

ε

M1 f0’0

g

ε

ε

ε

ε

0 fM10ε

fM1ε

ε

◮ La costruzione più generale (a sinistra) prevede 3nuovi stati, iniziale, finale e di raccordo.

◮ Lo stato di raccordo (lo stato h nella figura) vieneraggiunto dallo stato finale di M e prevede (medianteǫ-transizioni) il rientro in M o l’uscita.

◮ La costruzione di destra è utilizzabile nel caso dallostato iniziale di M1 esca una sola ǫ-transizione.

LFC



Esempio

◮ Costruiamo l’automa corrispondente all’espressioneregolare b(ab+ a∗c).

◮ La costruzione deve naturalmente rispettare leregole di precedenza, e dunque riflette la seguenteparentesizzazione: b((ab) + ((a∗)c)).

◮ Come primo passo costruiamo l’ASFND per ilriconoscimento di ab a partire dagli automi chericonoscono una sola lettera:

0 1ε a

2ε b

3 4

◮ Si noti che è stata operata una ridefinizione deglistati.

LFC



Esempio (continua)

◮ Come secondo passo costruiamo l’automa per ilriconoscimento di a∗ a partire dall’automa chericonosce a.

4

0 1ε

2 3aε

ε

ε

◮ Anche in questo caso si è operata una ridefinizionedegli stati (in modo da avere sempre 0 come statoiniziale).

LFC



Esempio (continua)◮ I passi successivi consistono nella creazione degli

automi per il riconoscimento, rispettivamente, di a∗c,di ab+ a∗c e infine di b(ab+ a∗c).

ε aε

ε

ε

ε c

ε a ε b

εε

ε

2

3 4 5 6

7 8 9

11 12 13 1410

ε b0 1

ε aε

ε

ε

ε c

ε a ε b

2 3 4

5 6 7

8 9 10 11 12

εε

ε1

0

6

0 1ε

2 3aε

ε

ε

4 5ε c

LFC



Il punto della situazione

◮ Data una qualunque espressione regolare E , siamoin grado (per il momento, “a mano”) di definire unASFND N = N (E) che riconosce il linguaggiodenotato da E .

◮ Dato N , siamo in grado, mediante gli algoritmi 2 e 3,di costruire un automa deterministico equivalente.

◮ Infine, mediante l’algoritmo 1 siamo in grado disimulare un qualunque automa deterministico.

◮ Complessivamente (trascurando per il momento ilnon piccolo dettaglio della costruzione manuale)disponiamo di un algoritmo che consente diaffermare, data un’espressione regolare E e unastringa X , se X è nel linguaggio denotato da E .

LFC



Simulazione diretta un ASFND

◮ L’alternativa agli algoritmi 2, 3 e 1 è la simulazionediretta dell’automa N (E) corrispondente allaespressione regolare E .

◮ L’algoritmo è una sorta di versione “on-line” deglialgoritmi citati.

◮ Per la simulazione, traiamo vantaggio dal fatto che,in base al procedimento di costruzione, l’automaN = N (E) ha come unica sorgente dinondeterminismo la presenza di stati dai quali sidipartono al più due biforcazioni per stato (etichettatecon ǫ).

LFC



Simulazione diretta un ASFND (continua)

◮ Questa proprietà consente in particolare dirappresentare internamente gli ASFND mediante trearray paralleli, di lunghezza pari al numero di stati,che chiameremo ic, state1, state2, con il seguentesignificato:

◮ ic[i] indica il carattere atteso nello stato i, che puòessere un simbolo di Σ o ǫ;

◮ state1[i] indica un possibile (o unico, nel casoic[i] 6= ǫ) stato successore;

◮ state2[i] indica un secondo possibile statosuccessore (nel caso ic[i] = ǫ).

LFC



Simulazione diretta un ASFND (continua)◮ Se ic[i] ∈ Σ, nello stato i l’automa “attende” un

carattere di Σ per transitare nello stato state1[i] (oaltrimenti arrestarsi con fallimento);

◮ se ic[i] = ǫ, nello stato i l’automa può transitare instate1[i] o in state2[i] senza consumare input;

◮ se esiste un solo stato successore etichettato ǫ sipone state1[i] = state2[i].

◮ Ad esempio, la porzione di automa

i

j

k

r

s

ǫ

ǫ

a

b

viene rappresentata comei kj

j

k

r s

ε a b

LFC



Algoritmo di simulazione

◮ Indicheremo con E gli stati da cui si dipartono (una odue) ǫ-transizioni.

◮ Indicheremo con C gli stati da cui si diparte un’unicatransizione etichettata con un simbolo di Σ.

◮ L’input di n caratteri si suppone memorizzato nelleprime n posizioni di un array T [1..n + 1], conT [n + 1] = $ (speciale marca di fine input, nonpresente nell’alfabeto).

◮ Diremo che uno stato q è compatibile con laporzione di input T [1..j] (per un qualche j ≥ 1) sel’automa può trovarsi nello stato q dopo aver letto iprimi j simboli di input.

◮ Una caratteristica della simulazione è che l’algoritmonon necessita di operare backtracking sull’input.

LFC



Algoritmo di simulazione (continua)

◮ L’algorimo usa una struttura dati D che, dopo lalettura dei primi j simboli dell’alfabeto, memorizzadistintamente gli stati compatibili con T [1..j − 1] equelli compatibili con T [1..j].

◮ Inizialmente j = 1 e D contiene il solo stato iniziale(diciamo q0), che è compatibile con T [1..j − 1] = ǫ.

◮ Al generico passo , l’algoritmo legge il j-esimocarattere di input ed estrae uno dopo l’altro da D glistati compatibili con T [1..j − 1].

◮ Sia q uno stato estratto, allora:◮ se q ∈ C ed esiste una transizione q → q′ etichettata

con il simbolo T [j], q′ viene inserito in D fra gli staticompatibili con T [1..j];

◮ se q ∈ E ed esistono le transizioni q → q′ e q → q′′,q′ e q′′ vengono inserite in D fra gli stati compatibilicon T [1..j − 1].

LFC



Algoritmo di simulazione (continua)

◮ Quando D non contiene più stati compatibili conT [1..j − 1], l’algoritmo incrementa j .

◮ Si noti che, prima dell’incremento, D contiene(eventualmente) solo stati compatibili con T [1..j].

◮ Dopo l’incremento di j , D contiene quindi(eventualmente) solo stati compatibili con T [1..j − 1].

◮ L’algoritmo termina in uno dei seguenti modi:◮ j = n + 1 e lo stato q estratto verifica q ∈ Qf , nel qual

caso l’input viene accettato;◮ D = Φ, nel qual caso l’input viene rifiutato (non fa

parte del linguaggio).

LFC



Esempio◮ Consideriamo il seguente semplice automa per il

riconoscimento del linguaggio a∗b, e supponiamoche la stringa in input sia T = aab.

0 1 2 3

4 5 6

ǫ ǫ a

ǫ

ǫ

ǫ b

◮ Le strutture dati importanti per capire ilfunzionamento dell’algoritmo sono il puntatore jall’input e la struttura dati D che rappresenteremocome coppia di sequenze, rispettivamente degli staticompatibili con T [1..j − 1] e degli stati compatibilicon T [1..j].

◮ Inizialmente j = 1 e D = 〈(0), ()〉.◮ Simuliamo passo passo il comportamento

dell’algoritmo.

LFC



Esempio (continua)

0 1 2 3

4 5 6

ǫ ǫ a

ǫ

ǫ

ǫ b

◮ Il primo ad essere estratto da D è lo stato 0, dalquale si diparte una transizione etichettata ǫ. Neconsegue che lo stato di arrivo (1) viene inseritonella struttura dati, che diviene D = 〈(1), ()〉.

◮ Viene estratto lo stato 1 ed inseriti gli stati 2 e 4, edunque D = 〈(4, 2), ()〉.

◮ Viene estratto lo stato (poniamo) 4 e viene inserito lostato 5: D = 〈(5, 2), ()〉.

LFC



Esempio (continua)

0 1 2 3

4 5 6

ǫ ǫ a

ǫ

ǫ

ǫ b

◮ Viene estratto lo stato (poniamo) 5 e poiché ilcarattere corrente di input (a) è diverso dal carattereche etichetta l’arco uscente dallo stato 5 (b), nonviene eseguita nessuna inserzione nella strutturadati: D = 〈(2), ()〉.

◮ La computazione procede poi nel modo seguente(usando un linguaggio sufficientementeauto-esplicativo):

◮ pop 2, insert 3: ⇒ D = 〈(), (3)〉;◮ increment j: ⇒ D = 〈(3), ()〉;◮ pop 3, push 1: ⇒ D = 〈(1), ()〉;

LFC



Esempio (continua)

0 1 2 3

4 5 6

ǫ ǫ a

ǫ

ǫ

ǫ b

◮ Segue computazione:◮ pop 1, push 2,4: ⇒ D = 〈(4, 2), ()〉;◮ pop 4, push 5: ⇒ D = 〈(5, 2), ()〉;◮ pop 5: ⇒ D = 〈(2), ()〉;◮ pop 2, insert 3: ⇒ D = 〈(), (3)〉;◮ increment j: ⇒ D = 〈(3), ()〉;◮ pop 3, push 1: ⇒ D = 〈(1), ()〉;◮ pop 1, push 2,4: ⇒ D = 〈(4, 2), ()〉;◮ pop 4, push 5: ⇒ D = 〈(5, 2), ()〉;◮ pop 5, insert 6: ⇒ D = 〈(2), (6)〉;◮ pop 2: ⇒ D = 〈(), (6)〉;◮ increment j: ⇒ D = 〈(6), ()〉;◮ pop 6: accept

LFC



La struttura dati deque

◮ La struttura dati D può essere implementataefficientemente usando una double ended queue osemplicemente deque.

◮ Una deque si comporta come un misto di pila e coda.◮ Le operazioni definite su di essa sono infatti push e

pop, che inseriscono ed estraggono dalla testa dellastruttura, e insert, che inserisce in coda.

◮ Per “simulare” l’esistenza di due sequenze distinte(rispettivamente, degli stati compatibili con T [1..j − 1]e con T [1..j]), e quindi anche l’operazione di“travaso” dalla seconda sequenza quando la prima sisvuota, è sufficiente utilizzare un simbolo speciale didelimitazione, poniamo #.

◮ Quando viene estratto # (mediante pop), l’algoritmosemplicemente lo re-inserisce in coda.

LFC



La struttura dati deque (continua)

◮ Consideriamo (con riferimento all’esempioprecedente) la situazione in cui D = 〈(), (3)〉.

◮ In tal caso, in realtà, la struttura interna (che èun’unica sequenza) è: (#,3).

◮ L’algoritmo esegue quindi sempre una pop all’iniziodi ogni passo e si rende conto che non ci sono piùstati compatibili con T [1..j − 1] quando il simboloestratto è #.

◮ Quando questo accade, l’algoritmo esegueimmediatamente una insert dello stesso simbolospeciale, producendo (nel caso esemplificato) lasequenza (3,#).

◮ L’algoritmo completo è riportato nella diapositivaseguente.

LFC



Algorithm 4 Simulazione diretta di un ASFND1: q ← pop()2: while (true) do3: if q = ′#′ then4: insert(q)5: q ← pop()6: if q = ′#′ then7: reject()8: j ← j + 19: if q ∈ Qf and j = n + 1 then

10: accept()11: if q ∈ C and ic[q] = T [j] then12: insert(state1[q])13: else if q ∈ E then14: push(state1[q])15: (state1[q] 6= state2[q]) and push(state2[q])16: q ← pop()

LFC



Confronto fra le due alternative◮ Data un’espressione regolare E , la costruzione

(manuale, per ora) che abbiamo discusso produceun ASFND N con Θ(|E|) stati (quanto vale lacostante nascosta?) e Θ(|E|) transizioni.

◮ Il costo della prima soluzione esaminata (algoritmi 2,3, 1) dipende in modo cruciale dal numero di stati(fino a 2|E|) dell’automa D.

◮ L’algoritmo 3 richiede tempo O(|E|) (e non O(|E|2)perché ogni transizione viene esaminata al più unavolta.

◮ Se n indica il numero di stati di D, l’algoritmo 2 costaO(n min {|Σ|, |E|} |E|), perché se |Σ| > |E| si puòsempre ridurre l’analisi ai soli simboli che compaiononella espressione di input.

◮ La simulazione dell’automa D (algoritmo 1), su inputX , richiede tempo Θ(|X |).

LFC



Confronto fra le due alternative (continua)

◮ Complessivamente, il costo della prima soluzione èO(n|E|2 + |X |).

◮ Il costo della seconda alternativa (algoritmo 4) èO(|E||X |) (bisogna però essere più accuratinell’implementazione!)

◮ Chiaramente, se n è molto grande, la secondaalternativa potrebbe essere preferibile.

◮ In molti casi pratici, tuttavia, n = Θ(|E|), e dunque, suinput lunghi, la prima soluzione risulta migliore.

◮ Se lo stesso automa deve essere applicato a piùstringhe (come proprio nel caso del parsing), laprima soluzione presenta ulteriori vantaggi.

LFC



Modifiche all’algoritmo di simulazione◮ Con lievi modifiche l’algoritmo di simulazione può

essere utilizzato per riconoscere stringhe descrittedall’espressione regolare (o meglio, dall’automacorrispondente) che compaiono in un generico testo.

◮ Le modifiche necessarie sono lasciate come utileesercizio per lo studente.

◮ Si badi che l’esercizio può essere risolto in almenodue modi, che illustreremo utilizzando il seguenteesempio, in cui l’espressione regolare è (ab)∗ e iltesto T in input è bbabababba:

◮ fermandosi non appena si trova una sottostringadescritta dall’espressione regolare (T [3..4]);

◮ fermandosi quando la sottostringa descrittadall’espressione regolare (se presente) non è piùestendibile (in questo caso T [3..8]).

◮ Nel contesto dell’analisi lessicale per i linguaggi diprogrammazione è di gran lunga preferibile laseconda soluzione.

LFC



Linguaggi non regolari◮ Dimostriamo che il linguaggio

L6 = {X ∈ {a,b}∗ : X = anbn, n ≥ 0} non è regolare.◮ La dimostrazione procede per assurdo.◮ SiaM un ASFD con m stati in grado di riconoscere

L6 e sia n tale che 2n > m.◮ Su input X = anbn esiste un cammino π (nel grafo

rappresentato dal diagramma di transizione) dallostato iniziale ad uno stato di accettazione tale che leetichette sugli archi del cammino formano X .

◮ Poichè 2n > m, il cammino non può esseresemplice, e dunque esiste un nodo p tale che ilcammino passa (almeno) due volte da p. Si veda laseguente figura (in cui ipotizziamo p 6= f ; il casop = f è analogo e lasciato allo studente):

0a b

fp

LFC



Linguaggi non regolari (continua)

◮ Ogni cammino che va dallo stato 0 allo stato f deveessere etichettato da una stringa di L6.

◮ In particolare il cammino π privato dei cicli su p deveessere etichettato da una stringa akbk , per unopportuno valore di k < n.

◮ Questo implica che il ciclo “intorno a p” deve essereetichettato da ahbh, con h = n − k > 0.

0a p f

bb

ab

◮ Questo a sua volta implica però che la stringaak+hbhahbh+k , che etichetta il cammino0 p p p f , viene accettata dall’automa, equesto è assurdo.

LFC



Esercizi proposti

◮ Si costruisca l’ASFND corrispondente (secondo lacostruzione vista) a ciascuna delle seguentiespressioni regolari:

◮ a∗b (a | b);◮ 1∗ (0 | ǫ) 1∗ (0 | ǫ) 1∗;◮ (ba | b)∗ ba∗ (ab | b).

◮ Si dimostri che nessuno dei seguenti linguaggi èregolari:

◮ {anbm|m > n};◮ {1n|n primo}.

LFC



Linguaggi formali e compilazione

Automi di riconoscimentoAutomi a stati finitiAutomi a pila

LFC



Automi a pila

◮ Gli automi a pila costituiscono un modello adeguatoper il riconoscimento dei linguaggi liberi.

◮ Un automa a pila (in inglese pushdown automaton oPDA) è un automa a stati finiti che dispone di unastruttura di memoria ausiliaria, costituita appunto dauna pila (non è consentito l’accesso casuale).

◮ Formalmente, rispetto ad un automa a stati finiti, ladefinizione di PDA include: (1) un alfabeto deisimboli che possono essere scritti sullo stac, e (2) ilsimbolo inizialmente sullo stack.

◮ Inoltre, la funzione di transizione mappa terne(q, a, Z ), dove q è uno stato dell’automa, a unsimbolo dell’alfabeto di input (oppure ǫ) e Z ilsimbolo sulla cima dello stack, in un insieme dicoppie 〈qi , αi〉, dove qi è uno stato e αi una stringa disimboli che vanno sullo stack.

LFC



Esempio

◮ Consideriamo il seguente automa a pila:◮ l’alfabeto di input è {a,b} (per semplicità,

supponiamo che l’input sia terminato dal simbolo $);◮ l’insieme degli stati è {0, 1, 2, 3}, con 0 stato iniziale

e {0, 3} insieme degli stati finali;◮ l’alfabeto dello stack è {E , A} ed E è il simbolo

inizialmente sullo stack;◮ la funzione di transizione è definita nel modo

seguente:

δ(0,a, E) = 〈1, AE〉 δ(1,a, A) = 〈1, AA〉δ(1,b, A) = 〈2, ǫ〉 δ(2,b, A) = 〈2, ǫ〉δ(2, $, E) = 〈3, ǫ〉

LFC



Esempio (continua)

◮ Una scrittura come, ad esempio, δ(0,a, E) = 〈1, AE〉,significa che se lo stato è 0, il simbolo di input è a e ilsimbolo rimosso dallo stack è E , allora l’automatransita nello stato 1, esegue due push sullo stack(dei simboli E e A, nell’ordine) oltre a far avanzare ilpuntatore di input.

◮ Il funzionamento di un automa a pila può esseredescritto da una sequenza di terne (detteconfigurazioni), che danno informazioni sullo statointerno, la porzione di input ancora da leggere e ilcontenuto dello stack.

◮ Per l’automa dell’esempio, su input aabb laconfigurazione iniziale è:

〈0,aabb, E〉

LFC



Esempio (continua)

◮ La funzione di transizione (che riportiamonuovamente per comodità:

δ(0,a, E) = 〈1, AE〉 δ(1,a, A) = 〈1, AA〉δ(1,b, A) = 〈2, ǫ〉 δ(2,b, A) = 〈2, ǫ〉δ(2, $, E) = 〈3, ǫ〉 )

determina le seguenti configurazioni successive:◮ 〈0,aabb$, E〉◮ 〈1,abb$, AE〉◮ 〈1,bb$, AAE〉◮ 〈2,b$, AE〉◮ 〈2, $, E〉◮ 〈3, ǫ, ǫ〉

LFC



Linguaggio riconosciuto da un automa a pila

◮ Data una stringa X in input, si dice che l’automariconosce X se l’input termina con l’automa in unostato finale (sono possibili altre definizioniequivalenti).

◮ Il linguaggio L(P) riconosciuto da un PDA P è quindidefinito (al solito) come l’insieme di tutte le stringhericonosciute da P.

◮ Non dovrebbe essere difficile convincersi chel’automa dell’esempio precedente riconosce L6.

◮ Si sarà probabilmente compresa anche la “tecnica”di riconoscimento.

◮ I caratteri a in input vengono trasformati in simboli Asullo stack;

◮ lo stack viene quindi svuotato togliendo una A perogni carattere b letto;

◮ se lo stack si svuota completamente con l’esaurirsidell’input la stringa è accettata.

LFC



Nondeterminismo

◮ La definizione data di PDA prevede che gli automipossano essere non deterministici.

◮ Sappiamo che, nel caso di automi a stati finiti, il nondeterminismo non aumenta la potenza di calcolo,che vuol dire che i due modelli riconoscono lo stessoinsieme di linguaggi (i linguaggi regolari).

◮ Non è così per gli automi a pila!◮ Ci sono infatti linguaggi riconosciuti da un PDA non

deterministico che non sono riconoscibili da un PDAdeterministico.

◮ Un esempio è il linguaggio delle stringhe palindrome(su un qualsiasi alfabeto).

◮ Si può dimostrare che l’insieme dei linguaggicontext-free contiene tutti e soli i linguaggiriconosciuti da PDA non deterministici.

Linguaggi Formali e Compilazione: Automi

Technology

Transcript of Linguaggi Formali e Compilazione: Automi