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

4.6.2 · Coding › Theory of Computation

YEH object EXISTS kyun karta hai?

Intuition Itni chhoti machine se kya fayda?

KYU: Hum jaanna chahte hain ki koi unbounded memory nahi wali machine kaun se problems solve kar sakti hai. Agar aap sirf "main $k$ situations mein se kismein hoon" yaad rakh sakte ho, toh aap kaun si languages (strings ke sets) recognize kar sakte ho? Jawab hai regular languages — exactly wahi jo regexes, lexical analyzers (tokenizers), search-and-replace, aur protocol checkers handle karte hain.

DFA kya "decide" karta hai: yeh poori string padhta hai aur ya toh accept state mein khatam hota hai (string ∈ language) ya reject state mein (string ∉ language). Toh DFA = language ke liye ek yes/no membership tester.

Yeh finite kaise rehta hai: yeh deterministic hai — ek given state se, ek given input symbol exactly ek next state force karta hai. Koi guessing nahi, koi choices nahi, koi branching nahi.

Formal 5-tuple — derive kiya, dump nahi kiya

Hum definition ko build karenge yeh poochh ke ki "ek aisi machine describe karne ke liye mujhe minimum kya chahiye?"

Mujhe jaanna hai...	toh main introduce karta hoon...	symbol
Machine kis situation mein ho sakti hai?	states ka ek finite set	$Q$
Woh kaun se symbols padh sakti hai?	ek finite input alphabet	$Σ$
(state, symbol) given ho toh main kahan jaata hoon?	ek total transition function	$δ$
Main shuru kahan se karta hoon?	ek single start state	$q_{0}$
Kaun si endings ka matlab "yes" hai?	accepting states ka ek set	$F$

δ ko poori strings tak extend karna (woh part jo zyaadatar notes skip karte hain)

$δ$ sirf ek symbol handle karta hai. Ek string $w$ process karne ke liye, hum extended transition function $\hat{δ} : Q \times Σ^{*} \to Q$ define karte hain, string length par recursion se:

State diagrams (Dual Coding: picture ↔ tuple)

Ek state diagram tuple ka visual twin hai:

circle = $Q$ mein ek state
double circle = ek accept state ( $\in F$ )
kahin se nahi aata arrow ("start") = $q_{0}$
labeled arrow $q a p$ = yeh fact ki $δ (q, a) = p$

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

Worked Example 1 — {0,1} par strings jo 1 mein KHATAM HOTI HAIN

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

State design (kya yaad rakhna hai): "ends in 1" ke liye sirf jo cheez matter karti hai woh hai last symbol dekha. Toh 2 states kaafi hain:

$q_{0}$ = "last symbol 0 tha, ya abhi tak koi symbol nahi" → reject
$q_{1}$ = "last symbol 1 tha" → accept

Tuple:

$Q = {q_{0}, q_{1}}$ , $Σ = {0, 1}$ , start $q_{0}$ , $F = {q_{1}}$
$δ (q_{0}, 0) = q_{0}$ , $δ (q_{0}, 1) = q_{1}$ , $δ (q_{1}, 0) = q_{0}$ , $δ (q_{1}, 1) = q_{1}$

Trace $w = 1011$ :

step	reading	from	to	Yeh step kyun?
1	1	$q_{0}$	$q_{1}$	1 dekha ⇒ yaad rakho "1 mein khatam hua"
2	0	$q_{1}$	$q_{0}$	ek 0 use mita deta hai ⇒ "0 mein khatam hua"
3	1	$q_{0}$	$q_{1}$	wapas "1 mein khatam hua"
4	1	$q_{1}$	$q_{1}$	abhi bhi 1 mein khatam hota hai

End state $q_{1} \in F$ ⇒ accepted. ✓ (aur indeed "1011" 1 mein khatam hota hai)

Worked Example 2 — 0's ki count EVEN hai (parity)

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

2 states kyun: parity ek yes/no fact hai; aapko actual count ki zaroorat nahi, sirf even vs odd. Yeh 80/20 insight hai — woh minimal memory rakho jo accept aur reject ko distinguish kare.

$Q = {E, O}$ ("even-so-far","odd-so-far"), start $E$ , $F = {E}$
$δ (E, 0) = O$ , $δ (O, 0) = E$ (ek 0 parity flip karta hai)
$δ (E, 1) = E$ , $δ (O, 1) = O$ (ek 1 irrelevant hai — self-loop)

Trace $w = 0100$ : $E 0 O 1 O 0 E 0 O$ . End $O \in / F$ ⇒ rejected. Check: $0100$ mein teen 0's hain (odd) ⇒ sahi reject kiya. ✓

Worked Example 3 — Forecast-then-Verify

Machine: $Q = {A, B, C}$ , $Σ = {a, b}$ , start $A$ , $F = {C}$ , $δ (A, a) = B, δ (A, b) = A, δ (B, a) = B, δ (B, b) = C, δ (C, a) = B, δ (C, b) = A .$

Recall Forecast: kya yeh DFA "abab" accept karta hai? (padhne se pehle predict karo)

Forecast: $C$ sirf "b" padhne par $B$ mein hote hue reach hota hai, yani "...ab" ending. Toh accept iff string "ab" mein khatam ho. $abab$ ka verify trace: $A a B b C a B b C$ . End $C \in F$ ⇒ accepted. Forecast confirm hua ("ab" mein khatam hota hai). ✓

Flashcards

DFA ke 5 components kya hain, order mein?

(Q, Σ, δ, q_{0}, F)

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

DFA transition function

δ

ki type signature kya hai?

δ : Q \times Σ \to Q

(total, single-valued).

Finite automaton ko deterministic kya banata hai?

Har (state, symbol) pair ke liye exactly ek next state hota hai —

δ

ek total function hai, koi choices nahi, koi

ε

-moves nahi.

\hat{δ} (q, ε)

aur

\hat{δ} (q, x a)

define karo.

\hat{δ} (q, ε) = q

;

\hat{δ} (q, x a) = δ (\hat{δ} (q, x), a)

DFA

M

string

w

kab accept karta hai?

Jab

\hat{δ} (q_{0}, w) \in F

L (M)

kya hai?

{w \in Σ^{*} : \hat{δ} (q_{0}, w) \in F}

— un sabhi strings ka set jo yeh accept karta hai.

"Regular language" kya hai?

Kisi DFA ke dwara recognized language.

State diagram mein double circle ka matlab kya hai?

Ek accept (final) state, yani

F

ka member.

State diagram mein start state ko kya mark karta hai?

Us state mein kahin se nahi aata ek arrow.

Agar state diagram mein kisi symbol ka arrow missing hai, toh DFA kya require karta hai?

Ek hidden total

δ

— asliyat mein ek dead/trap state ki taraf transition (khud par loop karta hai, non-accepting).

DFA

ε

accept karta hai iff kya?

Iff

q_{0} \in F

(start state accepting hai).

δ

aur

\hat{δ}

mein farq?

δ

ek symbol padhta hai;

\hat{δ}

recursion se poori string padhta hai.

Recall Feynman: ek 12-saal ke bacche ko DFA explain karo

Socho ek board game hai jisme kuch squares hain. Tum START square par shuru karte ho. Koi tumhe ek-ek karke letters ki string padhta hai. Har square ka ek rule hota hai: "agar tum a suno, us square par kood jao; agar b suno, is square par kood jao." Tum bas koodte rehte ho — tumhare paas koi notebook nahi, koi memory nahi sirf tum kaun se square par khade ho ke alawa. Jab letters khatam ho jaayein, neeche dekho: agar tum glowing (double-circle) square par ho, toh chillao "HAAN, yeh word meri club mein hai!"; warna "NAHI." Yahi ek DFA hai: ek finite hopping game jahan tum jis square par ho wahi tumhara poora brain hai.