Finite Automata (DFA and NFA)

Math for CS · Axiom Academy

States, transitions, and language recognition A Deterministic Finite Automaton (DFA) is the simplest model of computation. It has a finite number of states, reads input one symbol at a time, and makes exactly one transition per symbol. No choices, no memory beyond the current state. — the set of accept (final) states The key property: is a total function — for every state and every symbol, there is exactly one next state. No ambiguity, no dead ends (we add a "dead state" if needed). Read input symbols one at a time, left to right After reading symbol a in state q , move to state After reading the entire input string, accept if the current state is in F ; otherwise reject Design a DFA over that accepts strings with an even number of 1s (including zero 1s). Idea: We need to track whether the count of 1s seen so far is even or odd. Two states suffice. ( marks start state, * marks accept state) even odd odd even odd → Reject (odd is not an accept state) even odd odd odd even → Accept Example 2: Strings Ending in "01" Design a DFA over that accepts strings ending in "01". Idea: Track the last 1-2 characters seen. Three states: "nothing useful", "just saw 0", "just saw 01". The Extended Transition Function We extend to handle entire strings, not just single symbols. Define recursively: where w is a string and a is a single symbol. In words: process the string w first, then take one more step on symbol a . Then: M accepts w if and only if . Properties of Regular Languages

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