Automata Examples

Math for CS · Axiom Academy

Five fully worked constructions across DFAs, NFAs, PDAs, and Turing machines A DFA for Binary Strings Divisible by 3 Problem. Build a DFA over that accepts exactly the binary strings whose value (read most-significant-bit first) is divisible by 3. Step 1 — What state should we track? The only thing that matters about the prefix read so far is its value modulo 3. There are exactly three residues, , so the DFA needs three states. Step 2 — How does reading a bit change the residue? If the current value is n and we append a new bit b , the new value is 2n + b . So: Step 3 — Build the transition table The start state and accept state are both q_0 (the empty string has value 0, which is divisible by 3). Step 5 — Sanity check on input "110" 110_2 = 6 , which is divisible by 3, so the DFA should accept. Trace: . Final state is q_0 — accepted. An NFA for Strings Containing "ab" Problem. Build an NFA over that accepts exactly the strings that contain "ab" as a substring. Step 1 — Use nondeterminism to "guess" the position Reading the input, the NFA can stay in the start state until it nondeterministically guesses "ab starts here." It then commits to reading a then b , and after that loops in an accept state forever. Step 2 — Three states is enough q_0 : start, loops on a and b (still searching). q_1 : just read the a of our chosen ab . q_2 : just read the b of ab — accept and loop on everything.

This is the written version of the interactive lesson above. See the full Math for CS course.