Un'automaAssomigliano 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
- q0 = 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 q0, 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 q0, 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 è poplato 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 q0, 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. Appena trovo il coraggio metto qui la dimostrazione per esteso...:)
