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'

L'insieme delle stringhe riconosciute dall'automa \mathcal{A} forma un linguaggio formale chiamato linguaggio riconosciuto o linguaggio accettato 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 A è composto da tutte le stringhe x sull'alfabeto dato tali che, partendo dalla configurazione iniziale con la stringa x ed applicando iterativamente le relazioni di transizione, pervengono ad una configurazione accettante.

Il teorema di Kleene dimostra che la collezione dei linguaggi accettati 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