Automi finiti

Un automa finito è un modello di computer con una quantità estremamente limitata di memoria

• noto anche come macchina a stati finiti

Automa finito deterministico (DFA)

• alfabeto $\sum = \{a,b\}$
• insieme degli stati $Q= \{q_1,q_2,q_3\}$
• stato iniziale $q_1$
• stato finale $q_2$
• per ogni stato, se si legge un simbolo dell’alfabeto, il diagramma specifica in quale stato si transisce

Definizione formale

Un automa finito è una quintupla $(Q, \sum, \delta , q_0 F)$

• $Q$ è un insieme finito chiamato insieme degli stati
• $\sum$ è un insieme finito chiamato alfabeto
• $\delta : Q \times \sum \to Q$ è la funzione di transizione
• $q_0 \in Q$ è lo stato iniziale
• $F \subseteq Q$ è l’insieme degli stati accettanti (o finali)

Funzione di transizione

La funzione di transizione $\delta: Q \times \sum \to Q$ specifica per ogni stato e per ogni simbolo input, in quale stato si transisce

• $\delta(q_i,a) \in Q$ è lo stato in cui si troverà il DFA quando, trovandosi nello stato $q_i$, legge il simbolo $a$