Finite automata and regular languages

Prerequisites: Sets, functions, simple graphs, and basic programming.

Learning objectives

• Construct and trace a deterministic finite automaton.
• Explain nondeterminism using sets of active states.
• Distinguish finite memory from unbounded counting.

States summarize relevant history

A deterministic finite automaton, or DFA, has a finite set of states, an input alphabet, a transition function, a start state, and accepting states. It reads one symbol at a time. Its current state summarizes everything about the consumed prefix that can affect acceptance of the remaining input. Once the input ends, acceptance depends only on that final state.

To recognize binary strings containing an even number of ones, use two states: even and odd. Start in even. Reading zero leaves the state unchanged; reading one switches states. Accept in even. On input 1011, the states are even, odd, odd, even, odd, so the string is rejected. The empty string is accepted because it contains zero ones and no transition changes the start state.

A proof follows a loop invariant: after each prefix, the state agrees with the parity of the number of ones in that prefix. The transition rules preserve that fact, and the accepting-state rule matches the language definition. An automaton diagram without this connection is merely a proposed machine, not an explanation of its correctness.

Nondeterminism describes possible paths

A nondeterministic finite automaton, or NFA, may have several possible next states, including transitions that consume no input. It accepts when at least one complete path ends in an accepting state. This is not a claim that a physical computer guesses the right path for free. A deterministic simulation tracks the set of all possible current states, including states reachable through empty transitions.

The subset construction converts an NFA to a DFA whose states are subsets of NFA states. There can be up to 2^n subsets for n original states, though many may be unreachable. DFA and NFA recognize the same class of languages, called regular languages; their representations can have very different sizes.

Finite memory has a boundary

A fixed automaton can remember parity or a remainder modulo a fixed number. It cannot remember an arbitrary exact count with infinitely many possible values. The language consisting of n a symbols followed by n b symbols for any nonnegative n is not regular. Intuitively, different a-prefix lengths require distinguishable future behavior: the suffix b^i should complete a^i but not a^j for i different from j. A finite number of states cannot distinguish all such prefixes. This argument connects machine memory to language structure and motivates stack-based recognizers for nested syntax.

Practice problem

Construct a DFA for binary strings that contain an even number of ones and end in zero. Give a precise meaning for each state, identify the start and accepting states, and trace the empty string, 0, 11, and 110. Explain why tracking only parity is insufficient. Your design may use more states than the minimum, but every transition must be defined. Finally describe how to test all strings of length at most four against a direct specification.

Worked solution

Use states combining parity with a Boolean flag indicating whether the consumed prefix ends in zero. Start at (even,false), since the empty string does not end in zero. On symbol zero, keep parity and set the flag true; on one, flip parity and set the flag false. Accept only (even,true). The empty string rejects, 0 accepts, 11 rejects despite even parity, and 110 accepts. Parity alone cannot distinguish 11 from 110, so it lacks information required by the specification. Enumerate binary strings for lengths zero through four and compare automaton acceptance with the direct predicate “count of ones is even and the string ends in zero.” State invariants prove the construction generally; finite enumeration can expose coding mistakes in the transition table.

Check your understanding

When does an NFA accept an input?

• Every possible path accepts.
• At least one path consumes the entire input and ends in an accepting state.
• Its first explored path accepts any prefix.

Explanation

Nondeterministic acceptance is existential over complete paths, including allowed empty transitions.

Why can a DFA track a count modulo five but not every exact nonnegative count?

• Modulo five has only five possible summaries, while exact counts need unbounded distinguishable states.
• DFAs cannot read repeated symbols.
• Modulo counting requires no state at all.

Explanation

Finite-state memory can encode a fixed finite set of remainders but not infinitely many distinguishable counts.

Primary reading

• Automata, Computability, and Complexity: MIT OpenCourseWare

Open the study and save your work →