Finite Automaton

Finite Automaton (FA)

A finite automaton is a Finite State Machine which also has an additional Set of accepting states $F$. Unlike a general FSM, an FA has a defined set of accepting states ($F$) that determine whether an input string is accepted or rejected. FAs are used specifically for language recognition.

Definition

Formally, an FA is a 5-tuple $(Q,\Sigma ,\delta ,q_0,F)$:

1. $Q$: a finite Set of states
2. $\Sigma$: a finite Alphabet
3. $\delta :Q\times (\Sigma \cup \{ϵ\})\to \mathcal{P}(Q)$: a transition Relation
4. $q_0\in Q$: the start state
5. $F\subseteq Q$: a set of accepting states

Symbols:

• Power Set ($\mathcal{P}$)
• Cartesian Product ($\times$)
• Empty String ($\epsilon$)

Human: An FA is just a FSM that says “yes” or “no” to a String. If after consuming the whole input, the machine ends in a state belonging to $F$, the input is accepting, or not, it is rejected.

• For a DFA, $\delta :Q\times \Sigma \to Q$ is a true Function (exactly one next state).
• For an NFA, $\delta :Q\times (\Sigma \cup \{ϵ\})\to \mathcal{P}(Q)$ may produce multiple next states, or none, and can include $ϵ$-moves.