Introduction to Theory of Computation

Languages as decision problems

Fix a finite alphabet Sigma. A string is a finite sequence of alphabet symbols, including the empty string. A language is any set of strings. This simple definition unifies tasks such as recognizing valid variable names, checking balanced brackets and deciding whether encoded programs halt. Keep a language separate from its representation: a regular expression, automaton or grammar describes a language, and different descriptions may denote exactly the same set of strings.

References: 2026–27 calendar alignment with linked Winter 2015 Carleton notes · Maheshwari and Smid: Introduction to Theory of Computation, public Carleton notes

Deterministic finite automata and invariants

A DFA stores only its current state while consuming the input left to right. To design one, state what each state remembers about the prefix already read. For binary strings with an even number of ones, use states Even and Odd; a zero preserves the state and a one switches it. The start and accepting state is Even, so the empty string is accepted. This state invariant gives a direct induction proof of correctness.

References: 2026–27 calendar alignment with linked Winter 2015 Carleton notes · Maheshwari and Smid: Introduction to Theory of Computation, public Carleton notes

Nondeterminism does not enlarge regular languages

An NFA may have several possible transitions or transitions that consume no symbol. It accepts if at least one complete path accepts. The subset construction simulates all currently possible NFA states as one DFA state. This can produce exponentially many states, so equivalence of expressive power does not mean equivalent description size. When tracing an NFA, maintain a set of possible states and include epsilon-reachable states before consuming the next input symbol.

References: 2026–27 calendar alignment with linked Winter 2015 Carleton notes · Maheshwari and Smid: Introduction to Theory of Computation, public Carleton notes

Proving a language is not regular

To use the pumping lemma, assume regularity, choose a word based on the promised pumping length, and handle every permitted split. The adversary chooses the split, not the proof writer. For a^n b^n, choose a^p b^p. The pumpable segment lies entirely among the first p a symbols; pumping it changes the a count without changing the b count. The contradiction excludes regularity, but the lemma does not prove a language regular.

References: 2026–27 calendar alignment with linked Winter 2015 Carleton notes · Maheshwari and Smid: Introduction to Theory of Computation, public Carleton notes

Grammars, stacks and structural recursion

A context-free grammar rewrites one nonterminal at a time. The grammar S -> aSb | epsilon generates a^n b^n by nesting matched symbols. A pushdown automaton uses a stack to remember unbounded structured information, unlike a finite automaton. For balanced brackets, push openings and match them against closings. Ambiguity means a string has more than one parse tree; it is a property of a grammar and is not the same as uncertainty in a nondeterministic run.

References: 2026–27 calendar alignment with linked Winter 2015 Carleton notes · Maheshwari and Smid: Introduction to Theory of Computation, public Carleton notes

Recognizers, deciders and the halting barrier

A Turing machine can manipulate an unbounded tape, allowing a general model of computation. A decider halts on every input with the correct answer; a recognizer must accept members but may loop on nonmembers. The halting problem rules out a universal procedure deciding whether an arbitrary encoded program stops. This is a limitation on all algorithms under the model, not merely a claim that a particular machine is slow or lacks memory.

References: 2026–27 calendar alignment with linked Winter 2015 Carleton notes · Maheshwari and Smid: Introduction to Theory of Computation, public Carleton notes

Reductions transfer impossibility

To show a target language B undecidable, transform instances of a known undecidable language A into B so that answers are preserved. If a decider for B existed, the transformation followed by that decider would decide A. The direction is crucial: reducing B to A only shows B is no harder than A. In a proof, describe the transformation, prove its termination and establish both directions of the yes-instance correspondence.

References: 2026–27 calendar alignment with linked Winter 2015 Carleton notes · 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.

• 2026–27 calendar alignment with linked Winter 2015 Carleton notes ↗Course scope · 2026–27
• Maheshwari and Smid: Introduction to Theory of Computation, public Carleton notes ↗Supplementary primary reference
• Carleton COMP 3803 Winter 2015 full course notes ↗Historical public lecture notes · Winter 2015