Automa a stati finiti deterministico

Da Wikipedia, l'enciclopedia libera.

Nella teoria del calcolo, un automa a stati finiti deterministico (ASFD) o deterministic finite automaton (DFA) è un automa a stati finiti dove per ogni coppia di stato e simbolo in ingresso c'è una ed una sola transizione allo stato successivo.

Definizione formale[modifica | modifica wikitesto]

Un ASFD è una quintupla \mathcal{A} = \left \langle \Sigma, S, \delta, s_0, F \right \rangle con:

  • \Sigma = \{a_0, a_1, \ldots, a_n\} insieme finito di simboli chiamato alfabeto
  • S = \{s_0, s_1, \ldots, s_m\} insieme finito di stati
  • \delta : S \times \Sigma \to S funzione di transizione
  • s_0 \in S stato iniziale
  • F \subseteq S insieme di stati finali

Dato un ASFD \mathcal{A} = \left \langle \Sigma, S, \delta, s_0, F \right \rangle, una configurazione di \mathcal{A} è una coppia (s, x) , dove s è uno stato e x una stringa dell'alfabeto.

Una configurazione (s, x) è detta:

  • iniziale se s è lo stato iniziale, s = s_0 ;
  • finale se la stringa in input è vuota, x = \varepsilon ;
  • accettante se la stringa in input è vuota e l'automa si trova in uno stato finale, x = \varepsilon e s \in F .

La funzione di transizione induce una relazione di transizione \vdash tra due configurazioni, che associa ad una configurazione dell'automa la configurazione successiva.
Dato un ASFD \mathcal{A} = \left \langle \Sigma, S, \delta, s_0, F \right \rangle e due configurazioni (s, x) e (s', y) di \mathcal{A}, avremo tra loro una relazione di transizione (s, x) \vdash_\mathcal{A} (s', y) se valgono:

  • esiste un simbolo a \in \Sigma tale che x = ay
  • \delta(s, a) = s'

Una stringa x \in \Sigma^{*} è accettata dall'ASFD \mathcal{A} se, partendo dalla configurazione iniziale con la stringa ed applicando iterativamente le relazioni di transizione, si perviene ad una configurazione accettante. L'insieme delle stringhe accettate dall'automa forma un linguaggio formale chiamato linguaggio riconosciuto dall'automa. Possiamo quindi dire che L(\mathcal{A}) = \{x \in \Sigma^{*} | (s_0, x) \vdash_\mathcal{A}^* (s, \varepsilon), s \in F\}, ovvero che il linguaggio riconosciuto dall'ASFD è composto da tutte le stringhe sull'alfabeto dato per cui l'automa termina in uno stato finale.

Il teorema di Kleene dimostra che la collezione dei linguaggi riconosciuti da automi a stati finiti deterministici coincide sia con la collezione dei linguaggi regolari che con i linguaggi definiti da espressioni regolari.

Le espressioni regolari sono chiamate anche espressioni razionali e di conseguenza i linguaggi che esse forniscono sono detti linguaggi razionali; questi termini sono giustificati dal fatto che questi oggetti si possono studiare con metodi algebrici, più precisamente mediante semigruppi finiti.[senza fonte]

Funzione delta estesa[modifica | modifica wikitesto]

Un modo alternativo per descrivere il comportamento dell'automa è quello di definire la funzione di transizione estesa che estende la funzione di transizione dai simboli alle stringhe. Indichiamo la nuova funzione come \bar{\delta} : (S \times \Sigma^{*} ) \to S.

La sua definizione viene data induttivamente sulla lunghezza della stringa.

  • Base: \bar{\delta} (q, \varepsilon) = q.
  • Ipotesi induttiva: \bar{\delta} (q, x) = p.
  • Passo induttivo: \bar{\delta} (q, \omega) = \bar{\delta} (\bar{\delta} (q, x), a) = \bar{\delta} (p, a) = r, con \omega = xa.

Sfruttando la funzione delta estesa è possibile ridefinire il linguaggio accettato dall'automa come:

L(\mathcal{A}) = \{x \in \Sigma^* | \bar{\delta} (s_0, x) \in F \}

Esempio[modifica | modifica wikitesto]

Il seguente esempio è una ASFD \mathcal{A}, con un alfabeto binario, che determina se l'input contiene un numero pari di zeri.

\mathcal{A} = \left \langle \Sigma, S, \delta, s_0, F \right \rangle con:

  • \Sigma = \{0, 1\} alfabeto binario
  • S = \{S_1, S_2\} stati
  • s_0 = S_1 stato iniziale
  • F = \{S_1\} stati finali
Automa a stati finiti dell'esempio
  • \delta = \left\{\begin{matrix}
\delta (S_1, 0) = S_2 \\
\delta (S_1, 1) = S_1 \\
\delta (S_2, 0) = S_1 \\
\delta (S_2, 1) = S_2\end{matrix}\right.

La tabella di transizione è la seguente:

0 1
S1 S2 S1
S2 S1 S2

Semplicemente, lo stato S_1 rappresenta lo stato in cui abbiamo sempre un numero pari di zeri nell'input, mentre S_2 indica un numero dispari di zeri. Un 1 in input non cambia lo stato dell'automa. Quando l'input termina, lo stato mostrerà se l'input conteneva un numero pari di zeri, o no.

Da questo ASFD possiamo ricavare la grammatica regolare che genera il linguaggio regolare riconosciuto dall'ASFD:

S_1 \to 0S_2\; |\; 1S_1\; |\; 1\; |\; \varepsilon
S_2 \to 0S_1\; |\; 1S_2\; |\; 0

Il linguaggio riconosciuto da \mathcal{A} può essere descritto dal linguaggio regolare dato dalla seguente espressione regolare:

1^*(01^*01^*)^*

Bibliografia[modifica | modifica wikitesto]

  • Giorgio Ausiello, Fabrizio d’Amore; Giorgio Gambosi, Linguaggi, Modelli, Complessità, Franco Angeli Editore, 2003, ISBN 88-464-4470-1.
  • (EN) finite state machine (FSM) in Hargrave's Communications Dictionary, Hoboken, Wiley, 2001.
  • (EN) Sequential machine in Encyclopedia of Computer Science, Hoboken, Wiley, 2003.
  • (EN) John E. Hopcroft, Rajeev Motwani; Jeffrey D. Ullman, Finite Automata in Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 15 luglio 2006, ISBN 978-0-321-46225-1.
  • (EN) Martin Davis, Ron Sigal; Elaine J. Weyuker, Finite Automata in Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science, Morgan Kaufmann, 17 febbraio 1994, ISBN 978-0-12-206382-4.

Voci correlate[modifica | modifica wikitesto]

Teoria degli automi: linguaggi formali e grammatiche formali
Gerarchia di Chomsky Grammatica formale Linguaggio Automa minimo
Tipo-0 (illimitato) Ricorsivamente enumerabile Macchina di Turing
(illimitato) Ricorsivo Decider
Tipo-1 Dipendente dal contesto Dipendente dal contesto Automa lineare
Tipo-2 Libera dal contesto Libero dal contesto Automa a pila ND
Tipo-3 Regolare Regolare A stati finiti
Ciascuna categoria di linguaggio o grammatica è un sottoinsieme proprio della categoria immediatamente sottostante.
Informatica Portale Informatica: accedi alle voci di Wikipedia che trattano di Informatica