Foundations — Finite automata — DFA - formal definition (5-tuple), state diagrams

Before you can read $M=(Q,\Sigma ,\delta ,q_0,F)$ or $\hat{\delta }(q_0,w)\in F$, every one of those little marks must mean something you can see. Below we earn each symbol, in an order where each rests on the one before it.

1. A set and the curly braces $\{\}$

Picture: a bag with a few labelled marbles inside. $\{0,1\}$ is a bag holding one marble marked 0 and one marked 1.

Why the topic needs it: four of the five parts of a DFA are sets — the states $Q$, the alphabet $\Sigma$, and the accept states $F$ are literally bags of things, and even the start state $q_0$ is one marble pulled from the $Q$ bag.

2. "Element of" $\in$ and "subset" $\subseteq$

Picture: $\in$ is one marble pointing into a bag; $\subseteq$ is a small bag nested inside a big bag.

Why the topic needs it:

• $q_0\in Q$ — the start state is one of the machine's states.
• $F\subseteq Q$ — the accepting (glowing) states are some of all the states.
• Acceptance is decided by the test "$\hat{\delta }(q_0,w)\in F$": did we finish inside the glowing bag?

3. Symbols, an alphabet $\Sigma$, and strings

Picture: think of $\Sigma$ as the keyboard — the only keys allowed. A string is what you typed: a row of key-presses read strictly left to right.

Why the topic needs it: the machine reads members of ${\Sigma }^{\ast }$. The empty string $\epsilon$ is the sneaky edge case — a DFA accepts $\epsilon$ iff the start state is already glowing, so you must know $\epsilon$ exists and has length $0$.

4. A function and the arrow $\to$

Picture: a vending machine. Press one button (input), get exactly one item (output). Same button → same item, every time.

Why the topic needs it: $\delta$ is a function. If it were allowed to give a set of next states, or to leave some buttons dead, you'd have an NFA — see NFA — nondeterministic finite automata — not a DFA.

5. The Cartesian product $\times$ — pairing two bags

Picture: a grid. Rows are states, columns are symbols; every cell is one pair $(\text{state},\text{symbol})$.

Why the topic needs it: the transition rule reads a pair — "which state am I in AND which symbol did I read". That input type is exactly $Q\times \Sigma$, so $\delta :Q\times \Sigma \to Q$ means "feed the machine a (state, symbol) cell of the grid, receive the next state".

6. Putting the arrows on a picture — the state diagram

Picture: a board-game map. Squares are states; the labelled arrows are the movement rules; you always know which square you're on.

Why the topic needs it: the diagram and the 5-tuple are the same object in two languages. Reading one off the other is the core skill of the whole topic.

7. Recursion — how one-step $\delta$ grows into whole-string $\hat{\delta }$

Picture: climbing down a staircase. Each step "process the string $xa$" = "first process the shorter string $x$, then take one more footstep on $a$". The bottom stair is $\epsilon$ (nothing left to process).

Why the topic needs it: acceptance is defined as $\hat{\delta }(q_0,w)\in F$. Without recursion you have no meaning for "run the whole word", only "read one letter".

The prerequisite map

Every arrow says "you need the left idea before the right one makes sense". Notice how sets feed almost everything, and how the whole tower converges on the DFA 5-tuple.

Where these foundations go next

Once you own this vocabulary, the parent note DFA — formal definition becomes readable line by line. From there the ideas branch into Regular expressions, NFA — nondeterministic finite automata and its bridge Subset construction (NFA → DFA), the limits proved by Regular languages and the Pumping Lemma, the tidy-up of DFA minimization (Myhill–Nerode), and the real-world payoff in Lexical analysis / tokenizers.

Equipment checklist

Test yourself — cover the right side and answer aloud.