Automa a stati finiti deterministico

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.

Esempio di ASFD

Definizione formaleModifica

Un ASFD è una quintupla   con:

  •   insieme finito di simboli chiamato alfabeto
  •   insieme finito di stati
  •   funzione di transizione
  •   stato iniziale
  •   insieme di stati finali

Dato un ASFD  , una configurazione di   è una coppia  , dove   è uno stato e   una stringa dell'alfabeto.

Una configurazione   è detta:

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

La funzione di transizione induce una relazione di transizione   tra due configurazioni, che associa ad una configurazione dell'automa la configurazione successiva.
Dato un ASFD   e due configurazioni   e   di  , avremo tra loro una relazione di transizione   se valgono:

  • esiste un simbolo   tale che  
  •  

Una stringa   è accettata dall'ASFD   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  , 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 estesaModifica

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  .

La sua definizione viene data induttivamente sulla lunghezza della stringa.

  • Base:  .
  • Ipotesi induttiva:  .
  • Passo induttivo:  , con   (dove   e  ).

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

 

EsempioModifica

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

  con:

  •   alfabeto binario
  •   stati
  •   stato iniziale
  •   stati finali
 
Automa a stati finiti dell'esempio
  •  

La tabella di transizione è la seguente:

0 1
S1 S2 S1
S2 S1 S2

Semplicemente, lo stato   rappresenta lo stato in cui abbiamo sempre un numero pari di zeri nell'input, mentre   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:

 
 

Il linguaggio riconosciuto da   può essere descritto dal linguaggio regolare dato dalla seguente espressione regolare:

 

BibliografiaModifica

  • 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 correlateModifica

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 sovrastante.
  Portale Informatica: accedi alle voci di Wikipedia che trattano di Informatica