Finite Automaton First Example — Deterministic Finite Automata
🌱 What Exactly Is a DFA?**
Think of a DFA as a little robot with:
- a finite number of states (like different moods or positions),
- a starting state,
- some accepting states (states where the robot says “yes”),
- and a set of rules that tell it what to do when it sees each input symbol.
The robot reads a string (like “0101”), symbol by symbol.
Depending on what it reads, it moves from one state to another.
At the end, if it lands in an accepting state, the machine says:
“I accept this string.”
Otherwise, it rejects the string.
🎯 A First Simple Example
Let’s create a tiny DFA that accepts all binary strings (made of 0s and 1s)
that end with 1.
So if the string is “101”, it should accept.
If the string is “1100”, it should reject.
To design this DFA, imagine the machine watching the last symbol of the string.
We only need two states:
- q0 — means “I have not seen a 1 at the end (so far, string ends with 0)”
- q1 — means “I have seen a 1 at the end”
Whenever we read a new symbol, we update our belief about how the string ends.
- If we read 1, the last symbol is now 1 → move to q1.
- If we read 0, the last symbol is now 0 → move to q0.
That’s it. Very simple.
The accepting state will be q1 because if the last symbol is 1, the machine should say “yes”.
🎨 Original DFA Diagram (ASCII)
(DFA for strings ending with 1)
---------------------------------------------------
0 1
+-------------+ ----------------------+
| | |
v | v
+-----------+ | +----------------+
| |<------+ | |
---> | q0 |--------------------> | q1 |
| (start) | 1 | (accept) |
+-----------+ +----------------+
^ |
|------------------0----------------|Explanation of the diagram:
- q0 is the start state.
- If the machine sees a 1, it goes to q1.
- If the machine sees a 0, it stays or returns to q0.
- q1 is the accepting state because it represents strings that end with 1.
- From q1, if we see a 0, we return to q0 because now the string ends with 0.
Once the input is finished, if the machine is in q1, it accepts the string.
If it’s in q0, it rejects.
🧠 Walking Through an Example
Let’s input the string 1011.
Start at q0
- Read 1 → go to q1
- Read 0 → go to q0
- Read 1 → go to q1
- Read 1 → stay in q1
We end in q1 → ACCEPT.
Another string: 1000
Start at q0
- Read 1 → go to q1
- Read 0 → go to q0
- Read 0 → stay in q0
- Read 0 → stay in q0
We end in q0 → REJECT.
🌟 Why This Example Matters
This tiny DFA is usually one of the very first examples students learn.
It shows:
- how states represent “memory”,
- how transitions update that memory,
- how acceptance depends on the final state,
- and how simple rules can describe specific patterns in strings.
Even though DFAs feel simple, they are incredibly important.
They form the foundation of:
✔ lexical analysis in compilers
✔ text pattern matching
✔ digital circuits
✔ communication protocols
✔ and deeper concepts in Theory of Computation like regular languages and regular expressions
Once you understand this small example, you can build much more powerful automatons.
About the Author
