linguaggi formali e compilazione: automi
Post on 27-Jul-2015
2.467 Views
Preview:
TRANSCRIPT
LFC
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
Linguaggi formali e compilazioneCorso di Laurea in Informatica
A.A. 2008/2009
LFC
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
Linguaggi formali e compilazione
Automi di riconoscimentoAutomi a stati finitiAutomi a pila
LFC
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
Linguaggi formali e compilazione
Automi di riconoscimentoAutomi a stati finitiAutomi a pila
LFC
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
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
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
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
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
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
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
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
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
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
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
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 diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
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
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
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
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
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
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
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
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
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
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
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
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
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 diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
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
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
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
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
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
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
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
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
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
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
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
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
La cosiddetta “subset construction” (continua)
◮ 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
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
La cosiddetta “subset construction” (continua)
◮ 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
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
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
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
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
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
Esempio di subset construction (continua)
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
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
Esempio di subset construction (continua)
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
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
Esempio di subset construction (continua)
◮ 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
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
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
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
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 diriconoscimentoAutomi a stati finiti
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
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
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
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
Generalità delle ǫ-transizioni
◮ La porzione di automa
0
1
2
a
a
è equivalente a
0
1′
2′
1
2
ǫ
ǫ
a
a
LFC
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
Generalità delle ǫ-transizioni
◮ La porzione di automa
0
1
2
3
aaa
◮ è equivalente a
0
1′
2′
1
2′′
3′′
2
3
ǫ
ǫ
a
ǫ
ǫ
a
a
LFC
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
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 diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
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 diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
Esempi
◮ La grammatica corrispondente all’automa M5 è
Aq0 → a | aAq0 | bAq1 | ǫ
Aq1 → bAq1 | ǫ
◮ La grammatica corrispondente all’automa M3 è
Aq0 → 0Aq1
Aq1 → 1Aq2 | 0Aq3
Aq2 → 1Aq2 | 0Aq3
Aq3 → ǫ
◮ La grammatica corrispondente all’automa Mparity è
Aq0 → 0Aq0 | 1Aq1 | ǫ
Aq1 → 1Aq0 | 0Aq1
LFC
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
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 diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
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
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
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
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
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
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
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
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
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
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
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
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
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
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
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
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
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
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
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
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
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
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
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
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
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
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
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
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
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
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
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
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
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
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
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
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
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
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
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
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
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
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
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
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
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
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
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
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
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
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
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
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
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
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
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
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
Linguaggi formali e compilazione
Automi di riconoscimentoAutomi a stati finitiAutomi a pila
LFC
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
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
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
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
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
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
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
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
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
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
Automi diriconoscimentoAutomi a stati finiti
Automi a pila (pushdown)
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.
top related