DFA Simulation: Tracing Input for Acceptance

Hello! Welcome to the fourth lesson in our course on finite state machines.

Introduction

In our last lesson, we mastered the skill of expressing a Deterministic Finite Automaton (DFA) using its formal 5-tuple definition: $M = (Q, Σ, δ, q_{0}, F)$ . This gave us a precise, mathematical way to describe a machine.

Today, we'll bring that definition to life. Our goal is to trace the computation of a DFA on an input string to determine if it's accepted or rejected. This is the fundamental process that allows a DFA to "decide" whether a string belongs to the language it recognizes. We will see how the machine consumes an input string, symbol by symbol, moving from one state to another according to its transition function, $δ$ .

How a DFA Computes

At its heart, a DFA's computation is a simple, deterministic process:

The machine starts in the designated start state, $q_{0}$ .
It reads the input string one symbol at a time, from left to right.
For each symbol, it consults the transition function, $δ$ , to determine which state to move to next based on its current state and the input symbol.
This continues until the entire string has been read.
After the last symbol is processed, the machine stops. If its final state is one of the accept states (a member of the set $F$ ), the string is accepted. Otherwise, the string is rejected.

Let's watch this process in action with a couple of clear examples.

Deterministic Finite Automata (Example 1)

This video from Neso Academy provides a clear, step-by-step trace of a DFA's computation on two different input strings. It shows how the machine's state changes with each input symbol and how the final state determines the outcome.

Watch the two examples from 05:58 to 09:29. The first example (05:58 - 07:31) traces the accepted string '001', and the second (07:31 - 09:29) traces the rejected string '101'. Pay close attention to how the current state and the next input symbol dictate the move at each step.

The video provides a great visual intuition for the tracing process. To make this process rigorous, especially when we need to prove that a machine behaves in a certain way, we can use a more formal notation.

Formalizing the Trace

As a mathematics student, you'll appreciate that we can describe the state of the machine at any point in its computation with a precise notation. This is often called an instantaneous configuration (or instantaneous description). It's a pair that captures the machine's current state and the portion of the input string that it has not yet read.

We write an instantaneous configuration as: [current_state, remaining_input]

For example, if a machine is in state $q_{2}$ and still needs to process the string 101, the configuration is $[q_{2}, 101]$ .

To show a transition from one configuration to the next, we use the "yields" symbol, $⊢$ . The expression $[q_{i}, a x] ⊢ [q_{j}, x]$ means that from state $q_{i}$ with the string $a x$ remaining, the machine reads the symbol $a$ , moves to state $q_{j}$ (because $δ (q_{i}, a) = q_{j}$ ), and has the string $x$ left to read.

The following resource introduces this formal notation and provides a complete example.

LECTURE 23 - Computation Tracing

This PDF document from a Rutgers University CS course formalizes the concept of computation tracing. It introduces the instantaneous configuration notation and the 'yields' symbol.

Read the section titled '10.1.1 Computation Tracing'. Focus on understanding the notation '[current state, unused string]' and how the ⊢ symbol is used to represent a single step in the computation. Note the formal definition of acceptance at the end of the section.

A Worked Example with Formal Notation

Let's connect the visual trace from the video with the formal notation from the reading. We'll use the same DFA and trace the accepted string "001".

DFA Example I: Tracing an Input String — This DFA has a start state A, an accept state B, and a non-accepting state C. It is designed to accept any string over the alphabet {0, 1} that begins with a '0'.

The DFA's components are:

$Q = {A, B, C}$
$Σ = {0, 1}$
$q_{0} = A$
$F = {B}$
$δ$ is defined by the diagram's arrows (e.g., $δ (A, 0) = B$ , $δ (B, 1) = B$ , etc.).

Trace for input string "001":

The computation starts in the initial configuration $[A, 001]$ .

$[A, 001] ⊢ [B, 01]$
- Reasoning: The machine is in state $A$ and reads a 0. The transition function is $δ (A, 0) = B$ . The new state is $B$ , and the remaining string is 01.
$[B, 01] ⊢ [B, 1]$
- Reasoning: The machine is in state $B$ and reads a 0. The transition function is $δ (B, 0) = B$ . The new state is $B$ , and the remaining string is 1.
$[B, 1] ⊢ [B, ϵ]$
- Reasoning: The machine is in state $B$ and reads a 1. The transition function is $δ (B, 1) = B$ . The new state is $B$ , and the remaining string is empty, denoted by $ϵ$ .

The computation is finished. The machine ended in state $B$ . Since $B \in F$ , the string "001" is accepted.

We can summarize the entire computation using the $⊢^{*}$ symbol, which means "yields in zero or more steps":
$[A, 001] ⊢^{*} [B, ϵ]$
Because the computation ended in a final state, the string is accepted.

Your Turn: Trace a Computation

Now it's time to practice. Let's use the DFA from the exercise in our last lesson.

States: $Q = {0, 1, 2}$
Alphabet: $Σ = {0, 1}$
Start State: $q_{0} = 0$
Accept States: $F = {0}$
Transition Function ( $δ$ ):

$δ$	0	1
$\to * 0$	0	1
1	2	0
2	1	2

Your task is to trace the computation for the following two strings using the formal [state, remaining_string] notation. For each string, write out the sequence of configurations and state whether the string is accepted or rejected.

Input string: "110"
Input string: "0111"

Take your time to work through the steps. When you're ready, check your work against the solution below.

Click here to see the solution

1. Trace for "110"

$[0, 110]$ (Initial configuration)
$⊢ [1, 10]$ (since $δ (0, 1) = 1$ )
$⊢ [0, 0]$ (since $δ (1, 1) = 0$ )
$⊢ [0, ϵ]$ (since $δ (0, 0) = 0$ )

The computation ends in state $0$ . Since $0 \in F$ , the string "110" is accepted.

2. Trace for "0111"

$[0, 0111]$ (Initial configuration)
$⊢ [0, 111]$ (since $δ (0, 0) = 0$ )
$⊢ [1, 11]$ (since $δ (0, 1) = 1$ )
$⊢ [0, 1]$ (since $δ (1, 1) = 0$ )
$⊢ [1, ϵ]$ (since $δ (0, 1) = 1$ )

The computation ends in state $1$ . Since $1 \in / F$ , the string "0111" is rejected.

Conclusion

In this lesson, you've learned the crucial process of how a DFA computes. By tracing the sequence of states, you can definitively determine whether any given input string is accepted or rejected by the machine.

Key Takeaways:

A DFA's computation is a step-by-step process of reading an input string and changing states according to the transition function $δ$ .
A string is accepted if the DFA is in an accept state ( $\in F$ ) after reading the entire string. Otherwise, it is rejected.
The formal notation using instantaneous configurations [state, remaining_input] and the yields symbol $⊢$ provides a rigorous way to document a computation.

Now that you can both formally define a DFA and trace its execution, you have a solid understanding of its mechanics. In the next lesson, we will focus on the relationship between the two main representations of a DFA: we will learn to construct a transition table from a state diagram and vice versa. This will further solidify your ability to work with and describe these machines.

Recommended resources