Deterministic Finite Automata (DFA) Fundamentals and Examples

Fundamental Characteristics of Deterministic Finite Automata (DFA)

• A deterministic finite automata (DFA) is defined as a finite-state machine that processes (or parses) a given string composed of characters or symbols from an alphabet.

• Based on the input string, the machine either accepts or rejects the input by following a uniquely determined sequence of states.

• The term "deterministic" signifies that each specific input string results in a unique sequence of states.

• At any given moment during the parsing of a string, the automata can exist in one, and only one, state.

The Five-Tuple Formal Definition of a DFA

A Deterministic Finite Automata is formally defined as a five (5) tuple containing the following components:

• $Q$: A finite set of individual elements known as the states. Examples of sets for $Q$ include:

  • $Q = \{A, B, C, \dots\}$
  • $Q = \{S_1, S_2, S_3, \dots\}$
  • $Q = \{1, 2, 3, \dots\}$
  • $Q = \{q_0, q_1, q_2, \dots\}$

• $\Sigma$: A finite set called the alphabet, which consists of the symbols used for input. Examples include:

  • $\Sigma = \{0, 1\}$
  • $\Sigma = \{a, b, c\}$

• $f: Q \times \Sigma$ or $\delta: Q \times \Sigma \rightarrow Q$: The transition function. This function dictates the movement from one state to another state when the machine receives a specific input symbol. An example transition might be denoted as $\delta: A \rightarrow B$.

• $q_0 \in Q$: The initial state or start state where the processing of a string begins.

• $F \subseteq Q$: The set of final or accept states. In visual representations, final/accepting states are distinguished by a double circle.

Methods of DFA Representation

DFAs are commonly represented using two primary methods:

• Transition Diagrams: A visual flowchart-like representation of states (circles) and transitions (arrows).
• Transition Tables: A tabular format showing the resulting state for every possible combination of current state and input symbol.

Deterministic Finite Automata: Example 1

This DFA is designed to accept all strings that conclude with the symbol $1$. Accepted strings include $01$, $101$, $11$, $1011$, and $111$.

• State sequences for accepted strings:

  • For string $w = 01$, the sequence is: $s_1 \rightarrow s_1 \rightarrow s_2$
  • For string $w = 101$, the sequence is: $s_1 \rightarrow s_2 \rightarrow s_1 \rightarrow s_2$
  • For string $w = 11$, the sequence is: $s_1 \rightarrow s_2 \rightarrow s_2$
  • For string $w = 111$, the sequence is: $s_1 \rightarrow s_2 \rightarrow s_2 \rightarrow s_2$
  • For string $w = 1011$, the sequence is: $s_1 \rightarrow s_2 \rightarrow s_1 \rightarrow s_2 \rightarrow s_2$

• Transition Table for Example 1:

Deterministic Finite Automata: Example 2

This DFA is designed to accept all strings that start with one or more occurrences of the symbol $0$ and conclude with the symbol $1$.

• State sequences for accepted strings:

  • For string $w = 01$, the sequence is: $s_1 \rightarrow s_2 \rightarrow s_3$
  • For string $w = 001$, the sequence is: $s_1 \rightarrow s_2 \rightarrow s_2 \rightarrow s_3$
  • For string $w = 0001$, the sequence is: $s_1 \rightarrow s_2 \rightarrow s_2 \rightarrow s_2 \rightarrow s_3$

• Transition Table for Example 2:

Deterministic Finite Automata: Example 3

This project involves designing a DFA that accepts strings starting with a $1$ followed immediately by one or more $0$s.

• Configuration of States:

  • The DFA contains four states in total: $s_1$, $s_2$, $s_3$, and $s_4$.
  • The start state ($q_0$) is $s_1$.
  • The accept or final state ($F$) is $s_3$.
  • State $s_4$ functions as a "trap state." This state captures all inputs that deviate from the required pattern (e.g., strings that do not start with $1$ or do not follow the $1$ with a $0$).

• DFA Logic:

  • Strings following the pattern of a $1$ followed by one or more $0$s eventually land and stay in state $s_3$.
  • All other string variations are diverted to the trap state $s_4$, from which there is no escape to an accepting state.

• Transition Table for Example 3: