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

WHY does this object exist?

The formal 5-tuple — derived, not dumped

We will build the definition by asking "what do I minimally need to describe such a machine?"

I need to know...	so I introduce...	symbol
What situations can the machine be in?	a finite set of states	$Q$
What symbols can it read?	a finite input alphabet	$\Sigma$
Given (state, symbol), where do I go?	a total transition function	$\delta$
Where do I begin?	a single start state	$q_0$
Which endings mean "yes"?	a set of accepting states	$F$

Extending δ to whole strings (the part most notes skip)

$\delta$ only handles one symbol. To process a string $w$ , we define the extended transition function $\hat\delta : Q \times \Sigma^* \to Q$ by recursion on string length:

State diagrams (Dual Coding: picture ↔ tuple)

A state diagram is the visual twin of the tuple:

circle = a state in $Q$
double circle = an accept state ( $\in F$ )
an incoming arrow from nowhere ("start") = $q_0$
labeled arrow $q \xrightarrow{a} p$ = the fact $\delta(q,a)=p$

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

Worked Example 1 — strings over {0,1} that END in 1

Goal: $L = \{w : w \text{ ends in } 1\}$ .

State design (WHAT to remember): the only thing that matters for "ends in 1" is the last symbol seen. So 2 states suffice:

$q_0$ = "last symbol was 0, or no symbol yet" → reject
$q_1$ = "last symbol was 1" → accept

The tuple:

$Q=\{q_0,q_1\}$ , $\Sigma=\{0,1\}$ , start $q_0$ , $F=\{q_1\}$
$\delta(q_0,0)=q_0$ , $\delta(q_0,1)=q_1$ , $\delta(q_1,0)=q_0$ , $\delta(q_1,1)=q_1$

Trace $w=1011$ :

step	reading	from	to	Why this step?
1	1	$q_0$	$q_1$	saw a 1 ⇒ remember "ended in 1"
2	0	$q_1$	$q_0$	a 0 erases that ⇒ "ended in 0"
3	1	$q_0$	$q_1$	back to "ended in 1"
4	1	$q_1$	$q_1$	still ends in 1

End state $q_1 \in F$ ⇒ accepted. ✓ (and indeed "1011" ends in 1)

Worked Example 2 — number of 0's is EVEN (parity)

Goal: $L=\{w\in\{0,1\}^* : \#0(w)\text{ is even}\}$ .

WHY 2 states: parity is a yes/no fact; you never need the actual count, just even vs odd. This is the 80/20 insight — keep the minimal memory that distinguishes accept from reject.

$Q=\{E,O\}$ ("even-so-far","odd-so-far"), start $E$ , $F=\{E\}$
$\delta(E,0)=O$ , $\delta(O,0)=E$ (a 0 flips parity)
$\delta(E,1)=E$ , $\delta(O,1)=O$ (a 1 is irrelevant — self-loop)

Trace $w=0100$ : $E \xrightarrow{0} O \xrightarrow{1} O \xrightarrow{0} E \xrightarrow{0} O$ . End $O \notin F$ ⇒ rejected. Check: $0100$ has three 0's (odd) ⇒ correctly rejected. ✓

Worked Example 3 — Forecast-then-Verify

Machine: $Q=\{A,B,C\}$ , $\Sigma=\{a,b\}$ , start $A$ , $F=\{C\}$ , $\delta(A,a)=B,\ \delta(A,b)=A,\ \delta(B,a)=B,\ \delta(B,b)=C,\ \delta(C,a)=B,\ \delta(C,b)=A.$

Recall Forecast: does this DFA accept "abab"? (predict before reading)

Forecast: $C$ is reached only by reading "b" while in $B$ , i.e. an "...ab" ending. So accept iff string ends in "ab". Verify trace of $abab$ : $A\xrightarrow{a}B\xrightarrow{b}C\xrightarrow{a}B\xrightarrow{b}C$ . End $C\in F$ ⇒ accepted. Forecast confirmed (it ends in "ab"). ✓

Flashcards

What are the 5 components of a DFA, in order?

(Q,\Sigma,\delta,q_0,F)

— states, alphabet, transition function, start state, accept states.

What is the type signature of the DFA transition function

\delta

\delta : Q \times \Sigma \to Q

(total, single-valued).

What makes a finite automaton deterministic?

For every (state, symbol) pair there is exactly one next state —

\delta

is a total function, no choices, no

\varepsilon

-moves.

Define

\hat\delta(q,\varepsilon)

and

\hat\delta(q,xa)

\hat\delta(q,\varepsilon)=q

;

\hat\delta(q,xa)=\delta(\hat\delta(q,x),a)

When does a DFA

M

accept string

w

When

\hat\delta(q_0,w)\in F

What is

L(M)

\{w\in\Sigma^* : \hat\delta(q_0,w)\in F\}

— the set of all strings it accepts.

What is a "regular language"?

A language recognized by some DFA.

In a state diagram, what does a double circle mean?

An accept (final) state, i.e. a member of

F

In a state diagram, what marks the start state?

An arrow coming from nowhere into that state.

If a state diagram is missing an arrow for some symbol, what does a DFA require?

A hidden total

\delta

— really a transition to a dead/trap state (loops on itself, non-accepting).

Does a DFA accept

\varepsilon

iff what?

Iff

q_0\in F

(the start state is accepting).

Difference between

\delta

and

\hat\delta

\delta

reads one symbol;

\hat\delta

reads a whole string by recursion.

Recall Feynman: explain a DFA to a 12-year-old

Imagine a board game with a few squares. You start on the START square. Someone reads you a string of letters one at a time. Each square has a rule: "if you hear an a, hop to that square; if you hear a b, hop to this square." You just keep hopping — you have NO notebook, NO memory except which square you're standing on. When the letters run out, look down: if you're on a glowing (double-circle) square, you shout "YES, this word is in my club!"; otherwise "NO." That's a DFA: a finite hopping game where the square you're on is your whole brain.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, DFA ek bahut simple "machine" hai jiske paas sirf finite memory hai — na koi notebook, na koi extra storage. Uske paas kuch states hote hain (circles), aur jis bhi state pe vo abhi khada hai, wahi uski poori memory hai. Input string ek-ek symbol karke aata hai, aur har symbol pe machine ek fixed rule (transition function $\delta$ ) follow karke agle state pe jump karta hai. "Deterministic" ka matlab: har (state, symbol) ke liye sirf ek hi next state — koi guessing nahi, koi choice nahi.

Formal definition yaad rakhne ke liye 5 cheezein chahiye, yaani 5-tuple $(Q,\Sigma,\delta,q_0,F)$ : $Q$ = saare states, $\Sigma$ = alphabet (jo symbols read honge), $\delta$ = transition rule $Q\times\Sigma\to Q$ , $q_0$ = start state, aur $F$ = accept (final) states. String complete padhne ke baad agar machine kisi accept state ( $F$ ka member, diagram me double circle) pe khada hai, toh string accept, warna reject. Iska formal version $\hat\delta$ se aata hai: $\hat\delta(q,\varepsilon)=q$ aur $\hat\delta(q,xa)=\delta(\hat\delta(q,x),a)$ .

State diagram bas isi tuple ki picture hai — circle = state, double circle = accept, bahar se aati arrow = start, aur labelled arrow = $\delta$ ki ek line. Real life me ye important hai kyunki tokenizers, regex search, password/pattern checking — sab DFA jaisi cheez se chalti hain.

Ek common galti: agar diagram me kisi symbol ki arrow missing dikhe, mat socho "undefined hai". DFA me $\delta$ total hona chahiye — woh missing arrow asal me ek hidden "dead/trap state" ki taraf jaati hai. Aur dusri galti: $\varepsilon$ (empty string) ko bhulna mat — agar $q_0\in F$ hai toh empty string bhi accept hoti hai. Bas itna pakka rakho, baaki sab same logic pe chalta hai.