Defining DFAs: The 5-Tuple Formalism

From Identification to Formal Expression

In the last lesson, we pulled the five components out of a diagram. Now, we'll learn how to package them into a single, formal statement: $M=(Q,\Sigma ,\delta ,q_0,F)$. This formal definition is essential—it's what you would provide to a computer program or use as the basis for a mathematical proof.

To see this process in action, let's watch a detailed walkthrough.

Anatomy of the 5-Tuple

The video did a great job of constructing the formal definition from a diagram. Let's crystallize what we saw. For the DFA in the video, the full 5-tuple definition is written as:

$M=(Q,\Sigma ,\delta ,q_0,F)$

Where:

1. $Q=\{q_0,q_1,q_2,q_3\}$

   • This is the finite set of all states, which you identify from the circles in the diagram.

2. $\Sigma =\{0,1\}$

   • This is the finite set of input symbols, identified from the labels on the transition arrows.

3. $q_0$

   • This is the designated start state, a single element from $Q$.

4. $F=\{q_1,q_2\}$

   • This is the set of accept states, a subset of $Q$.

5. $\delta$

   • This is the transition function. As the video highlighted, the most common and clearest way to formally define $\delta$ is with a transition table. The table is a direct representation of the function $\delta :Q\times \Sigma \to Q$. For each state (row) and input symbol (column), the table entry gives the resulting state.

(Note: The arrow $\to$ denotes the start state, and the asterisk $\ast$ denotes an accept state. This is a common convention when presenting transition tables.)

By defining these five parts, we have a complete, formal specification of the machine.

An Alternative View and Example

The transition table is a great way to define $\delta$. Another way, which you might see in more theoretical texts, is to simply list all the input-output pairs of the function. Let's look at a resource that uses this style.

In the parity-checker example from the notes, the transition function was defined as:

• $\delta (q_0,0)=q_0$
• $\delta (q_1,0)=q_1$
• $\delta (q_0,1)=q_1$
• $\delta (q_1,1)=q_0$

This list fully defines the function $\delta$. For a machine with many states and a large alphabet, a transition table is generally more readable, but both methods are valid ways to express the function.

Your Turn: Formalize a DFA

Now it's time to put this into practice. Your task is to provide the complete 5-tuple definition for the DFA shown in the diagram below.

Please write out the full formal definition $M=(Q,\Sigma ,\delta ,q_0,F)$.

1. Define the set of states, $Q$.
2. Define the alphabet, $\Sigma$.
3. Identify the start state, $q_0$.
4. Define the set of accept states, $F$.
5. Define the transition function, $\delta$, using a transition table.

Take a few minutes to write this down. Once you're ready, you can check your answer against the solution below.

Conclusion

In this lesson, we solidified your understanding of the formal definition of a DFA. You learned how to take the components identified in a state diagram and express them as a complete and unambiguous 5-tuple, $M=(Q,\Sigma ,\delta ,q_0,F)$.

Key Takeaways:

• A DFA is formally specified by its 5-tuple. This definition is precise and forms the basis for all theoretical analysis.
• The transition function $\delta :Q\times \Sigma \to Q$ can be defined by listing all its mappings, but is most clearly and compactly represented by a transition table.
• Expressing a DFA formally involves defining each of the five components correctly using mathematical notation (e.g., sets for $Q$, $\Sigma$, and $F$).

Now that we have a solid grip on how to define a DFA, we are ready to see it in action. In the next lesson, we will trace the computation of a DFA on an input string. This will allow us to determine precisely whether a given string is accepted or rejected by the machine.