Theory of Automata

Descriptions, recognizers and equivalence

Regular expressions, NFAs and DFAs are different finite descriptions of regular languages. Conversion constructions show equality of expressive power, while their sizes can differ dramatically. To compare two DFAs, construct a product automaton that accepts when exactly one component accepts; the languages are equal precisely when no accepting product state is reachable. This turns a universal claim about infinitely many strings into a finite graph-reachability problem.

References: Carleton 4805 official calendar record · Maheshwari and Smid: Introduction to Theory of Computation, public Carleton notes

Distinguishable states and minimal automata

Two DFA states are distinguishable if some suffix is accepted from one but rejected from the other. States that no suffix can distinguish may be merged without changing the recognized language. First remove states unreachable from the start. Begin partition refinement by separating accepting from nonaccepting states, then split groups when a symbol leads to different groups. A minimal DFA retains only relevant distinctions about prefixes. The proof obligation concerns every possible future suffix, not just the examples used during testing.

References: Carleton 4805 official calendar record · Maheshwari and Smid: Introduction to Theory of Computation, public Carleton notes

Closure properties as construction tools

Regular languages are closed under union, intersection and complement. Product constructions combine automata for intersection, while complementation flips accepting states in a complete DFA. Context-free languages are closed under union and concatenation, but not general intersection or complement. They are closed under intersection with a regular language, which is useful for isolating a structured subcase. Always check the language class before applying a closure property in a proof.

References: Carleton 4805 official calendar record · Maheshwari and Smid: Introduction to Theory of Computation, public Carleton notes

Context-free grammars and ambiguity

A grammar's production rules can generate nested structures through recursion. For arithmetic expressions, E -> E + E | E * E | id permits multiple parse trees for id + id * id. Separate precedence levels to remove this source of ambiguity. Ambiguity belongs to a grammar; an inherently ambiguous language has no unambiguous context-free grammar. Showing one ambiguous grammar therefore does not establish inherent ambiguity of the language it generates.

References: Carleton 4805 official calendar record · Maheshwari and Smid: Introduction to Theory of Computation, public Carleton notes

Deterministic pushdown automata are more restrictive

A pushdown automaton extends finite control with a stack. Nondeterminism can guess where a phase changes, as in a palindrome with no central marker. A deterministic pushdown automaton must select transitions without conflicting alternatives under its input and stack conditions. Unlike finite automata, eliminating nondeterminism does reduce expressive power here. For a language such as w # reverse(w), the delimiter explicitly reveals when to switch from pushing symbols to checking them.

References: Carleton 4805 official calendar record · Maheshwari and Smid: Introduction to Theory of Computation, public Carleton notes

The Chomsky hierarchy and decision questions

The hierarchy organizes grammars and machines by expressive restrictions: regular, context-free, context-sensitive and unrestricted descriptions provide progressively broader models. A more expressive model does not guarantee that questions about its descriptions remain decidable. DFA equivalence is decidable, whereas general Turing-machine language equivalence is not. Keep membership questions about one string separate from equivalence, emptiness and universality questions about a whole described language; their difficulty can differ substantially.

References: Carleton 4805 official calendar record · Maheshwari and Smid: Introduction to Theory of Computation, public Carleton notes

Worked product proof and impossibility reasoning

Take one DFA tracking parity of the number of zeros and another tracking parity of the number of ones. Their product has four parity pairs. Accepting only the Even-Even pair recognizes strings with both counts even, proving this language regular by construction. For nonregularity or non-context-freeness, choose a suitable theorem and respect its quantifier order. A few failed candidate automata or grammars are never enough to prove that no description exists.

References: Carleton 4805 official calendar record · Maheshwari and Smid: Introduction to Theory of Computation, public Carleton notes

Practice & worked answers

Original exercises for this guide.

Public notes & references

Course sources establish the scope above. Reference materials support the explanations; linked lecture notes and books remain with their authors.

• Carleton 4805 official calendar record ↗Course scope · 2026–27
• Maheshwari and Smid: Introduction to Theory of Computation, public Carleton notes ↗Supplementary primary reference