DFA and NFA Trace and Acceptance

1. Tracing a Deterministic Finite Automaton (DFA)

The defining characteristic of a DFA is its determinism: for any given state and input symbol, there is exactly one next state. This means tracing a DFA is straightforward, as there is only a single computational path to follow.

The Intuitive Approach: Following the Path

The simplest way to trace a DFA is to start at the initial state and follow the arrows corresponding to the symbols in the input string, one by one.

Let's watch a clear, practical demonstration of this process. The following video first designs a DFA and then traces two different input strings through it, showing how one is accepted and the other is rejected.

As you saw, the process is:

1. Start at the initial state.
2. For each symbol in the input string (from left to right), follow the transition arrow labeled with that symbol to the next state.
3. After reading the last symbol, check your current state.
4. If the final state is an accept state (double circle), the string is accepted. Otherwise, it is rejected.

The Formal Approach: The Extended Transition Function

To formalize this process, we introduce the extended transition function, denoted as ${\delta }^{\ast }$. While the regular transition function, $\delta$, tells us the next state after reading a single symbol, ${\delta }^{\ast }$ tells us the final state after reading an entire string.

The definition of ${\delta }^{\ast }:Q\times {\Sigma }^{\ast }\to Q$ is as follows:

1. Base Case: ${\delta }^{\ast }(q,ϵ)=q$
   • Reading no symbols leaves the machine in its current state, $q$.
2. Recursive Step: ${\delta }^{\ast }(q,xc)=\delta ({\delta }^{\ast }(q,x),c)$
   • To find the state after reading string $xc$ (where $x$ is a string and $c$ is a symbol), you first find the state after reading $x$ (which is ${\delta }^{\ast }(q,x)$) and then apply the standard transition function $\delta$ for the final symbol $c$.

A DFA $M=(Q,\Sigma ,\delta ,q_0,F)$ accepts a string $w$ if and only if ${\delta }^{\ast }(q_0,w)\in F$.

2. Tracing a Nondeterministic Finite Automaton (NFA)

Tracing an NFA is fundamentally different. Due to nondeterminism, an NFA can be in a set of multiple states at once. When it reads a symbol, it follows all possible transitions from its current set of states to compute a new set of states. This is akin to exploring multiple computational paths in parallel.

The process of tracing an NFA involves tracking this evolving set of "active" states.

The Core Idea: Tracking Sets of States

The key steps for tracing an NFA are:

1. Start with a set of states containing just the initial state, $q_0$. Then, add all states reachable from $q_0$ using only $ϵ$-transitions. This is your initial set of active states.
2. For each symbol in the input string:
   a. For every state in the current active set, find all possible next states using the standard transition function $\delta$ for the current input symbol.
   b. Combine all these next states into a new set.
   c. For every state in this new set, add all states reachable from them using only $ϵ$-transitions. This final set is your new set of active states.
3. After reading the last symbol, look at the final set of active states.
4. If this final set contains at least one accept state (i.e., the intersection of your final set and the set of all final states $F$ is not empty), the string is accepted. Otherwise, it is rejected.

The Formal Approach for NFAs

Like with DFAs, we can formalize this process with an extended transition function, ${\delta }^{\ast }$. For NFAs, ${\delta }^{\ast }$ maps a state and a string to a set of states. Its definition is more involved because it must handle $ϵ$-transitions and sets of states.

The video below provides a rigorous, step-by-step application of the formal definition to trace an NFA. While the narration includes another language, the on-screen mathematics and diagrams are in English and are exceptionally clear.

The NFA acceptance condition can be stated formally: An NFA $M=(Q,\Sigma ,\delta ,q_0,F)$ accepts a string $w$ if and only if ${\delta }^{\ast }(q_0,w)\cap F\ne \varnothing$.

Conclusion

Today you learned how to execute, or "run," finite automata on input strings. This is the heart of what these machines do: they are computational devices for answering the question, "Is this string in the language?"

Key Takeaways:

• DFA Tracing: Follows a single, deterministic path. The machine is in exactly one state at any time. A string is accepted if this single path ends in an accept state. This can be formalized with the extended transition function ${\delta }^{\ast }$.
• NFA Tracing: Involves tracking an evolving set of possible states. The computation effectively branches, and we follow all paths in parallel. This process must also account for $ϵ$-transitions.
• NFA Acceptance: A string is accepted if the final set of active states contains at least one accept state.

Preview of the Next Lesson:
We've now seen that NFAs are often simpler to design, but their execution model (tracking sets of states) is more complex than a DFA's simple path. DFAs are simpler to execute but can be much more complex to design. This presents a trade-off. In the next lesson, we will resolve this by learning the subset construction algorithm, a powerful technique to convert any NFA into an equivalent DFA. This process formalizes the very tracing procedure you learned today for NFAs.