Deterministic Finite State Machines#

Definition: Deterministic Finite State Machine

A deterministic finite state machine (DFSM) or deterministic finite automaton (DFA) is a tuple \((\Sigma, S, s_0, \delta, F)\), where:

\(\Sigma\) is a finite, non-empty set known as the input alphabet;
\(S\) is a finite, non-empty set known as the set of states;
\(s_0 \in S\) is known as the initial state;
\(\delta\) is a function \(\delta: S \times \Sigma \to S\) known as the state-transition function;
\(F \subseteq S\) is known as the set of accepted states or the set of final states.

Definition: Extended Transition Function

Let \(\mathcal{S} = (\Sigma, S, s_0, \delta, F)\) be a finite state machine:

The extended transition function of \(\mathcal{S}\) is the function \(\hat{\delta}: S \times \Sigma^{\ast} \to S\) defined in the following way:

Base case: For each state \(s \in S\), we have \(\hat{\delta}(s, \varepsilon) = s\) where \(\varepsilon\) is the empty string;
Recursive case: For each state \(s \in S\), each string \(w \in \Sigma^{\ast}\) and each symbol \(a \in \Sigma\), we have \(\hat{\delta}(s, wa) = \delta(\hat{\delta}(s, w), a)\).

Definition: Acceptance and Rejection

Let \(\text{DFSM} = (\Sigma, S, s_0, \delta, F)\) be a deterministic finite state machine and let \(w \in \Sigma^{\ast}\).

We say that \(\text{DFSM}\) accepts \(w\) if the extended transition function yields an accepted state on \((s_0, w)\):

\[ \hat{\delta}(s_0, w) \in F \]

We say that \(\text{DFSM}\) rejects \(w\) if the extended transition function does not yield an accepted state on \((s_0, w)\):

\[ \hat{\delta}(s_0, w) \notin F \]