1.1DFA: the machine with no choices
The idea
A DFA reads a string once, left to right, always knowing exactly which state it is in. Its only memory is its state.
Think of it like this: A turnstile: it just remembers "locked" or "unlocked" and reacts to the next coin or push.
Why it exists
It is the simplest model of computation, and it shows precisely what can be done with a fixed, finite memory.
How it works
- Start in q₀ and read the first symbol.
- For each state and symbol there is exactly one next state.
- After the last symbol, accept if you are in a final state.
- Because the number of states is fixed, you cannot count unboundedly.
Worked example: Strings ending in "ab"
States q0 (nothing useful yet), q1 (just read a), q2 (just read ab). On baab: q0 →b q0 →a q1 →a q1 →b q2: ends in q2, accept.
Now play with it
- →Run
baab, thenaba, and watch the gold state move. - →Try the "even number of a's" machine and see two states are enough.
- Start: ε-closure of q0 = {q0}
- read "b" → {q0}
- read "a" → {q1}
- read "a" → {q1}
- read "b" → {q2}
- End of input and at least one active state is final: ACCEPT
Check yourself
A DFA has 5 states over {a, b}. How many transitions does it have?
Exam notes (the dense version)
A DFA is (Q, Σ, δ, q₀, F). From every state there is exactly one move on every symbol. Its only memory is the current state, so it can never count without a bound. A string is accepted if it ends in a final state.
Previous year questions: Finite Automata (DFA, NFA, ε-NFA) (6)
PYQs are grouped by topic, so this is the full set for Finite Automata (DFA, NFA, ε-NFA); try the ones that match this subtopic. Open all 6 on the topic page.