Formal Structures of DFAs and NFAs

Hello! Welcome to your second module. We're now moving from the abstract foundations of languages to the specific machines designed to recognize them.

In our last lesson, we introduced the big picture of automata theory. We learned that automata are abstract models of computation, with a hierarchy of power determined by their memory. We ended with an initial look at the formal 5-tuple definition of a Finite Automaton, $M = (Q, Σ, δ, q_{0}, F)$ , which serves as a mathematical blueprint for these machines.

This lesson drills down into the details of our first and simplest model. The learning outcome is to define the formal structures (5-tuples) of Deterministic and Nondeterministic Finite Automata (DFAs and NFAs). We will unpack what "deterministic" and "nondeterministic" mean and see how this core difference is captured precisely in their mathematical definitions.

1. Deterministic Finite Automata (DFA)

A Deterministic Finite Automaton is the most straightforward type of automaton. The "deterministic" nature means that for any given state and any given input symbol, there is exactly one state the machine will transition to. There is no ambiguity and no choice. This behavior is analogous to a well-defined function in programming: for a given input, you always get the same single output.

Formal Definition of a DFA

A DFA is formally defined as a 5-tuple $M = (Q, Σ, δ, q_{0}, F)$ , where:

$Q$ is a finite, non-empty set of states.
$Σ$ is a finite, non-empty set called the alphabet of input symbols.
$δ : Q \times Σ \to Q$ is the transition function. It takes the current state and the current input symbol and returns a single next state.
$q_{0} \in Q$ is the start state.
$F \subseteq Q$ is the set of accept states (or final states).

The most critical component here is the transition function, $δ$ . Its signature, $δ : Q \times Σ \to Q$ , mathematically enforces determinism: one state and one symbol map to exactly one resulting state.

To see how this formal definition connects to the state diagrams we've seen, the following video provides a clear walkthrough.

Finite State Machine (Finite Automata)

This video from Neso Academy will take you from an intuitive state diagram to the formal 5-tuple definition of a DFA, explaining each component with a concrete example.

Please watch from 01:43 to 10:39. Pay close attention to how the five components (Q, Σ, q₀, F, and δ) are extracted from the visual diagram and how the transition function δ is represented as a table.

As the video demonstrated, the transition function $δ$ can be fully described using a transition table. The rows represent states, the columns represent input symbols from the alphabet, and each cell contains the single destination state.

DFA Examples with Formal Definitions and Diagrams — This image provides a complete example of a DFA. It shows the state diagram, its corresponding 5-tuple formal definition, and the transition function represented as a table. This illustrates how all three representations describe the exact same machine.

Test your understanding!

Consider the DFA shown in the image above (the first example, M1). The alphabet is $Σ = {0, 1}$ . Write down the formal value of the transition function $δ (q_{1}, 1)$ and $δ (q_{2}, 0)$ .

Show answer

Looking at the transition table or the diagram:

$δ (q_{1}, 1) = q_{2}$ . When in state $q_{1}$ , reading a '1' moves the machine to state $q_{2}$ .
$δ (q_{2}, 0) = q_{3}$ . When in state $q_{2}$ , reading a '0' moves the machine to state $q_{3}$ .

2. Nondeterministic Finite Automata (NFA)

Now, let's relax the strict rule of determinism. What if a machine could explore multiple possibilities at once? This is the core idea behind a Nondeterministic Finite Automaton (NFA).

In an NFA, for a given state and input symbol, the machine can transition to:

Zero next states (the computation path "dies").
One next state (just like a DFA).
Multiple next states (the machine effectively "clones" itself, with each clone exploring a different path).

Furthermore, NFAs can have transitions on the empty string, $ϵ$ . This means the machine can change its state without consuming an input symbol. Given your background in building complex systems, you can think of this nondeterminism as conceptually similar to spawning multiple threads or processes to explore different execution paths simultaneously. The NFA as a whole accepts the input if any of these parallel paths ends in an accept state.

Formal Definition of an NFA

The formal definition of an NFA looks very similar to a DFA's, but with a critical modification to the transition function to accommodate nondeterminism.

An NFA is a 5-tuple $N = (Q, Σ, δ, q_{0}, F)$ , where $Q$ , $Σ$ , $q_{0}$ , and $F$ are the same as in a DFA. The difference lies in $δ$ :

$δ : Q \times (Σ \cup {ϵ}) \to P (Q)$ is the transition function.

Let's break down this new definition for $δ$ :

Domain: The input to the function is a pair from $Q \times (Σ \cup {ϵ})$ . This means it takes a state and either a symbol from the alphabet $Σ$ or the empty string $ϵ$ .
Codomain: The output is an element of $P (Q)$ , which is the power set of $Q$ . The power set of $Q$ is the set of all possible subsets of $Q$ . This allows the transition function to return a set of next states, which can be empty, contain one state, or contain multiple states.

The following video explains this concept very clearly, showing why the power set is necessary to formally define an NFA.

Formal Definition of Non-Deterministic Finite Automata (NFA)

This Neso Academy video introduces NFAs and masterfully explains why the transition function must map to the power set of states to capture the essence of nondeterminism.

Please watch from the beginning to 10:30. Focus on the differences from a DFA and the logic behind deriving the new transition function signature, δ: Q × Σ → 2^Q (the video uses 2^Q, which is another notation for the power set P(Q)).

As the video explained, if a machine has $k$ states, there are $2^{k}$ possible subsets of states it could transition to, hence the notation $2^{Q}$ or $P (Q)$ .

Formal Definition of NFA with State Diagram — This image shows a state diagram for an NFA and its corresponding 5-tuple definition. Note how the transition for state q1 on input '1' would be δ(q1, 1) = {q1, q2}, returning a set of states.

For a more rigorous textual definition, you can refer to the following resource.

q1 q2 q3 a b b a a, b

These lecture notes provide a concise, formal definition of an NFA, including ε-transitions.

Please read the sections 'Formal Definition of NFA' and 'Difference Between DFA and NFA'. This will solidify the mathematical definition and explicitly contrast it with the DFA's.

3. DFA vs. NFA: A Side-by-Side Comparison

The only distinction in their 5-tuple definitions is the transition function, but this single change has profound implications.

Feature	Deterministic Finite Automaton (DFA)	Nondeterministic Finite Automaton (NFA)
Number of Next States	Exactly one for each (state, symbol) pair.	Zero, one, or multiple for each (state, symbol) pair.
$ϵ$ -Transitions	Not allowed.	Allowed. Can change state without consuming input.
Transition Function $δ$	$δ : Q \times Σ \to Q$	$δ : Q \times (Σ \cup {ϵ}) \to P (Q)$
Interpretation	Follows a single, unique computation path for each input.	Follows multiple computation paths in parallel for each input.

Test your understanding!

Consider the NFA N1 from the Neso Academy video (LINK) you watched. The states are $Q = {a, b}$ and the alphabet is $Σ = {0, 1}$ .
What is the value of $δ (a, 0)$ ? What about $δ (b, 1)$ ?

Show answer

From state a, on input 0, there are transitions back to a and to b. So, $δ (a, 0) = {a, b}$ .
From state b, there are no outgoing transitions for input 1. So, $δ (b, 1) = \emptyset$ (the empty set).

This perfectly illustrates how the output of the NFA's transition function is a set of states.

Conclusion

In this lesson, we established the precise, formal definitions of the two main types of finite automata. This mathematical rigor is essential for proving properties about what these machines can and cannot do.

Key Takeaways:

A DFA is formally defined by the 5-tuple $(Q, Σ, δ, q_{0}, F)$ , where the transition function $δ : Q \times Σ \to Q$ maps to a single state, enforcing determinism.
An NFA is also defined by a 5-tuple, but its transition function $δ : Q \times (Σ \cup {ϵ}) \to P (Q)$ maps to the power set of states. This allows for zero, one, or many next states, as well as $ϵ$ -transitions.
The difference between their formal definitions lies entirely in the codomain and domain of the transition function $δ$ .

Preview of the Next Lesson:
Now that we have the formal blueprints for DFAs and NFAs, we can start building with them. In the next lesson, we will focus on bringing these definitions to life by constructing state transition diagrams for specific languages and tracing the execution of these machines on input strings to determine whether they accept or reject.

Recommended resources