Traduttori - Appunti del 19 marzo 2009

 Torna alla pagina di Traduttori

:: Traduttori - Appunti del 19 marzo 2009 ::

Automi

Discorsi introduttivi sugli automi sono stati fatti in mille materie diverse. Quello che interessa a noi è sapere a che cosa servono nell'ambito dei Traduttori.

Possiamo rappresentarli in diversi modi. Uno di questi consiste nell'immaginare un automa come una specie di macchina con una testina, la quale testina è posizionata su di un nastro. Questo nastro è composto da celle, ed ogni casella rappresenta un simbolo in input. La macchina legge il simbolo contenuto nella cella, cambia il proprio stato interno, ed avanza il nastro di una posizione.

Assomigliano un po' alle Macchine di Turing. Un altro modo per rappresentare un automa è quello dei pallogrammi, che si usano un po' dappertutto.

Definizione formale

Un automa A consiste in una quintupla:

 A = (Q, Σ, δ, q0, F)

ed ecco la spiegazione:

• Q = insieme finito di stati
• Σ = alfabeto
• q₀ = stato iniziale
• δ = funzione di transizione: Q x δ -> Q
• F = sottinsieme degli stati di Q, detti stati finali o di accettazione

La macchina parte nello sato q₀, e gli do in pasto il primo elemento della stringa di input. Le transizioni portano la macchina in uno stato o in un altro a seconda dell'input in arrivo e dello stato attuale.
Questa stringa di input viene accettata se, dopo aver percorso tutta la stringa di input, l'automa si trova in uno degli stati F, cioè stati di accettazione. Vediamo quindi che finalmente si attua l'idea, più volte menzionata nel corso delle precedenti lezioni, di riconoscitore di linguaggi.

Estensione della funzione di transizione

La funzione di transizione δ viene però in genere estesa, per facilitare (?) le cose. Si definisce quindi un'altra funzione:

 δ^ = Q * Σ* -> Q

Attenzione: in δ^ l'accento circonflesso è detto cap e dovrebbe stare sopra il δ, ma non ho trovato un modo per mettercelo... La funzione si chiama quindi delta cap.

La δ^ ci permette quindi di associare funzioni di transizione non solo ai singoli simboli, ma anche alle stringhe: posso quindi riconoscere interi linguaggi.

Linguaggi definiti dagli automi

Un linguaggio definito da un automa lo segno così:

 L(A) =  {w | δ^ (q0, w) ∈ a F}

e questa è la spiegazione: il linguaggio definito dall'automa A è quel linguaggio composto da tutte le stringhe w che vengono accettate dall'automa stesso. L'accettazione viene rappresentata dicendo che la funzione δ^, applicata alla stringa w, partendo dallo stato iniziale q₀, deve portare l'automa in uno stato finale appartenente agli stati di accettazione.

Definizione induttiva di δ^

Base induttiva:

 δ^(q, ε) = q

Vuol dire che, se sono in uno stato, e leggo la stringa vuota, non mi muovo da quello stato.

Passo induttivo:

 w = xa, dove x ∈ Σ* e a ∈ Σ
 δ^(q, xa) = δ(δ^(q, x), a)

Questo vuol dire che, data una stringa w composta da una stringa x e da un simbolo a, il risultato della funzione δ^ applicata ad essa consiste nell'applicare ricorsivamente la δ^ alla stringa x, e poi applicare la δ al simbolo a. Ricorrendo ricorrendo si arriva infine ad avere la δ^ come una sorta di "semplificazione" dell'applicazione ripetuta di δ ai singolo elementi di una stringa.

Automi non deterministici

Gli automi visti finora sono di tipo deterministico. In questo contesto, deterministico vuol dire che, a partire da un certo stato, applicando un certo input la δ^ mi conduce in un solo stato.

L'automa non deterministico invece ha una δ^ particolare, tale che a partire da uno stato, applicando un certo input, può portarmi in uno o più stati contemporaneamente. È come se, in presenza di quel particolare input arrivato in un certo stato, la macchina si sdoppiasse (o triplicasse etc.) in due diversi thread paralleli, ognuno dei quali va avanti per la sua strada.

La mia δ^ viene quindi ridefinita:

 δ^: Q x Σ* -> ℙ(Q)

dove ℙ(Q) rappresenta qualcosa come un insieme di stati.

Warning: definizione da migliorare...

Definizione induttiva di δ^ per automi non deterministici

Base induttiva:

 |w| = 0 => w = ε
 δ^(q, ε) = {q}

Vuol dire che se la cardinalità di una certa stringa è 0, allora quella stringa è vuota. La δ^ applicata ad una ε mi fa rimanere nello stesso stato in cui mi trovavo.
Il fatto che io segni lo stato di destinazione con {q} sta a significare che, come abbiamo visto qui sopra, la δ^ mi porta in un insieme di stati, e non in uno stato solo. In questo caso l'insieme di stati è popolato da un solo elemento, ma in generale un automa non deterministico può portarmi in un numero qualunque di stati.

Passo induttivo:

 w = xa, x ∈ Σ*, a ∈ Σ
 δ^(q, xa) = Unione, ∀ p ∈ δ^(q,x), δ(p,a)

Questo vuol dire che applico la δ ad ogni sottostringa di xa, e ottengo un insieme di stati, che uniti compongono il risultato della δ^

Riassumendo, la mia δ^ è una funzione che, dato uno stato e una stringa in input, mi porta in un insieme di stati contemporaneamente, e in linea teorica il mio automa non deterministico avvierà un'esplorazione parallela ed indipendente di ogni stato in cui la δ^ mi ha portato.

Linguaggi definiti dagli automi non deterministici

I linguaggi che vengono definiti, cioè riconosciuti, dagli automi non deterministici si rappresentano così:

 L(N) = { w | δ^(q0, w) ⊆ F}

Il significato è che una stringa w appartiene al linguaggio definito dal mio automa N se, applicando la δ^ a partire dallo stato q₀, almeno uno degli stati finali in cui mi trovo sarà uno stato di accettazione. Non tutti: almeno uno.

Equivalenza tra automi deterministici e automi non deterministici

I DFA e gli NFA (rispettivamente, automi deterministici e automi non deterministici) sono equivalenti: è sempre possibile rappresentare un automa in una delle due forme.

Il teorema di Rabin Scott dimostra proprio questo: se a partire da un NFA costruisco un DFA in un certo modo, ho la certezza che essi saranno equivalenti, ovvero riconosceranno come appartenenti al linguaggio le stesse stringhe, e nessun'altra.

Dimostrazione del teorema di Rabin Scott

Il teorema prevede di costruire in un certo modo, a partire da un NFA, un certo DFA, e poi dimostrarne l'equivalenza proprio in virtù di questa costruzione, detta costruzione per sottinsiemi.

In particolare, vogliamo che gli stati del DFA siano pari a tutti i sottinsiemi degli stati del NFA. La cardinalità dell'insieme dei sottinsiemi di un insieme (puff!) è 2ⁿ, e pertano mi aspetto di trovare 2ⁿ stati nel mio DFA così costruito. Informo però da subito che nella maggior parte dei casi saranno necessari molti meno stati.
Riassumendo, sto dicendo che il singolo stato del DFA è un insieme di stati dell'NFA.

A che cosa serve l'insieme dei sottinsiemi? Server per creare la mia funzione δ_D a partire dalla δ_N. Ecco come:

 δD(S, a) = U, ∀ p ∈ S, δN(p, a)

Il significato è il seguente: la funzione δ dell'automa deterministico porta, come al solito, da uno stato ad un altro stato a seconda dell'input a che le viene dato. Sappiamo altresì che la δ di un automa non deterministico invece porta ad un insieme di stati.
Orbene, la δ definita qui sopra dice che l'input a mi porta in uno stato, che è composto dall'unione di tutti gli stati raggiungibili con la δ non deterministica!

Ecco a che cosa serve dire che l'insieme degli stati del DFA è l'insieme dei sottinsiemi. L'NFA porterà ad un certo numero di stati, i quali saranno sottinsiemi dell'insieme totale degli stati dell'NFA. Pertanto, se lo stato del DFA rappresenta un sottinsieme degli stati del NFA, allora vuol dire che portano allo stesso punto.

La dimostrazione dell'equivalenza tra NFA e DFA così costruito avviene per induzione. Definiamo la nostra δ^:

 δ^D({q0}, w) = δ^N(q0,w)

Come vedete, la δ^_D agisce su {q₀}, e questa è la scrittura che mi dice che ho a che fare con un insieme. Infatti, come dicevo sopra e come ripeto ancora, i singoli stati del DFA sono tutti sottinsiemi degli stati del NFA.

Caso base: w = ε
Per definizione di δ^, sappiamo che con la stringa vuota non si va da nessuna parte, e pertanto:

 δ^D({q0}, ε) = δ^N(q0, ε) = {q0}

Le graffe sono qui per ricordarci che abbiamo a che fare con insiemi di insiemi.

Induzione: w = xa, in cui x è una stringa e a un singolo carattere.
Per ipotesi induttiva sappiamo che il caso base è valido per la stringa x:

 δ^D({q0}, x) = δ^N(q0, x)

Conosciamo inoltre la definizione di δ^:

 δ^D({q0}, xa) = δD(δ^D({q0},x), a)

Ricordate? La δ^ è definita come l'applicazione ricorsiva della δ ad ogni componente della stringa. Andate a vedere i vecchi appunti se non mi credete:)

Ma l'ipotesi induttiva vista sopra ci dice che δ^_D = δ^_N. Pertanto, possiamo riscrivere la formuletta del paragrafo precedente così:

 δ^D({q0}, xa) = δD(δ^N(q0,x), a)

Inoltre, sappiamo come abbiamo costruito la nostra δ^_D:

 δD(S, a) = U, ∀ p ∈ S, δN(p, a)

Riscrivendola con q₀ al posto di S avremo:

 δ^D({q0}, xa) = U, p ∈ δ^N(q0, x), δN(p, a)

e se siete stati attenti avrete visto che la parte a destra dell'uguale è la definizione di δ^_N! Ecco quindi che, avendo costruito l'automa D in quel modo, possiamo infine dire:

 δ^D = δ^N

---

Torna alla pagina di Traduttori