Theory of Computation: Complete Beginner-Friendly Notes

Theory of Computation (TOC) is a core subject in computer science that explains what computers can solve, how they solve it, and where their limits begin. Instead of studying a particular programming language or device, TOC uses mathematical models such as finite automata, pushdown automata, and Turing machines.

The subject may feel abstract at first, but its ideas appear in real systems: compilers check program syntax, search tools use pattern matching, network protocols follow state-based rules, and algorithm analysis helps us estimate whether a solution will scale.

What You Study in TOC

  • Formal languages: Sets of strings that follow defined rules.
  • Automata theory: Abstract machines that recognize languages.
  • Computability theory: Problems that can or cannot be solved by an algorithm.
  • Complexity theory: The time and memory needed to solve problems.

Why Theory of Computation Matters

  • Builds the foundation for compiler design and programming-language theory.
  • Helps you understand regular expressions and syntax checking.
  • Explains why some tasks are impossible to automate perfectly.
  • Develops the reasoning used in algorithm design and analysis.

Formal Languages

A formal language is a collection of strings formed using a fixed set of symbols and well-defined rules. Unlike English or Hindi, a formal language is designed to remove ambiguity. A string either belongs to the language or it does not.

Basic Terms

  • Alphabet (Σ): A finite set of symbols. For example, Σ = {0, 1}.
  • String: A finite sequence of symbols from an alphabet, such as 0101.
  • Empty string (ε): A string containing no symbols.
  • Language (L): Any set of strings over an alphabet.
  • Σ*: The set of all possible strings over Σ, including ε.
  • Σ+: The set of all non-empty strings over Σ.

Example

Let Σ = {a, b}. Then Σ* contains ε, a, b, aa, ab, ba, bb, aaa, and every other finite combination of a and b.

Operations on Languages

  • Union: L1 ∪ L2 contains strings present in either language.
  • Intersection: L1 ∩ L2 contains strings common to both languages.
  • Concatenation: L1L2 joins a string from L1 with a string from L2.
  • Kleene star: L* allows zero or more repetitions of strings from L.
  • Complement: L̅ contains strings in Σ* that are not in L.

Grammars in Formal Languages

A grammar is a rulebook for generating valid strings in a language. It starts with a special symbol and repeatedly applies production rules until only terminal symbols remain.

Formal Definition of a Grammar

Grammar G is written as G = (V, T, P, S), where:

  • V is a finite set of variables or non-terminals.
  • T is a finite set of terminals.
  • P is a finite set of production rules.
  • S is the start symbol, where S ∈ V.

Simple Grammar Example

Grammar: G = ({S, A}, {a, b}, P, S)

Rules:

S → aA
A → bA | ε

This grammar produces: a, ab, abb, abbb, ...
Therefore, the language is {abn | n ≥ 0}.

Finite Automata

A finite automaton is a simple machine that reads an input one symbol at a time and changes from one state to another. It has limited memory, so it is useful for patterns that do not require counting an unlimited number of items.

Finite automata recognize regular languages. They are widely connected with lexical analysis in compilers, input validation, simple protocol design, and pattern matching.

Deterministic Finite Automaton (DFA)

In a DFA, every state has exactly one next state for each input symbol. There is no guessing and no ε-transition.

DFA Definition

A DFA is a 5-tuple: M = (Q, Σ, δ, q0, F)

  • Q: finite set of states
  • Σ: input alphabet
  • δ: transition function, Q × Σ → Q
  • q0: initial state
  • F: set of accepting or final states

Non-Deterministic Finite Automaton (NFA)

An NFA may have multiple possible next states for the same input symbol, no transition for a symbol, or transitions that consume no input at all (ε-transitions). It is often easier to design an NFA for a pattern, even though a computer can implement the equivalent DFA.

Key fact: DFA and NFA have the same computational power. Both recognize exactly the regular languages.

DFA Example: Strings Ending in 01

Consider a DFA over {0, 1} that accepts every binary string ending with 01, such as 01, 101, and 0001.

Current State Input 0 Input 1
q0 (start) q1 q0
q1 q1 q2
q2 (final) q1 q0

State q2 is accepting because reaching it means the last two symbols read were 0 and 1. If another symbol appears, the machine moves again because the string may no longer end in 01.

Regular Expressions and Regular Languages

A regular expression is a compact way to describe a pattern of strings. In TOC, the basic operations are union, concatenation, and Kleene star. Modern programming tools also commonly use shorthand symbols such as + and ?.

Expression Meaning Examples Accepted
a* Zero or more a's ε, a, aa, aaa
(a|b)* Any string made from a and b ε, ab, baba
a(a|b)*b Starts with a and ends with b ab, aab, abab
(0|1)*00(0|1)* Contains 00 as a substring 00, 1001, 000
Important relationship: Every regular expression can be converted into an NFA, and every DFA/NFA has an equivalent regular expression.

Pumping Lemma for Regular Languages

The pumping lemma is mainly used to prove that a language is not regular. It says that sufficiently long strings in a regular language must contain a section that can be repeated or removed without leaving the language.

If L is regular, then there is a pumping length p such that every string w in L with |w| ≥ p can be written as w = xyz, where:

  1. |xy| ≤ p
  2. |y| ≥ 1
  3. xyiz belongs to L for every i ≥ 0

Example: Why {anbn | n ≥ 0} Is Not Regular

  1. Assume the language is regular and let p be its pumping length.
  2. Choose w = apbp.
  3. Since |xy| ≤ p, the substring y contains only a's.
  4. Pump y once more by choosing i = 2.
  5. The new string has more a's than b's, so it is not in the language.
  6. This is a contradiction; therefore, the language is not regular.
Remember: Failing the pumping-lemma conditions proves non-regularity. Satisfying the conditions alone does not prove that a language is regular.

Context-Free Grammars and Pushdown Automata

Regular languages cannot handle many nested patterns, such as balanced parentheses. Context-free grammars (CFGs) are more powerful and are designed for such structures. They are especially important in programming-language syntax.

CFG Example: Balanced Parentheses

S → (S) | SS | ε

This grammar can generate valid strings such as ε, (), ()(), (()), and (()()). It cannot generate invalid strings such as )( or (().

A pushdown automaton (PDA) is like a finite automaton with an additional stack. The stack allows it to remember unmatched opening brackets or other nested information.

  • When reading an opening parenthesis, a PDA can push a symbol onto the stack.
  • When reading a closing parenthesis, it pops one symbol from the stack.
  • If the input ends with the stack properly balanced, the string is accepted.
Key fact: A language is context-free if and only if it can be generated by a CFG; equivalently, it can be recognized by a PDA.

Turing Machines and Computability

A Turing machine is a theoretical machine with a read/write tape, a head that moves across the tape, and a finite set of states. Unlike a finite automaton, it can use the tape as unlimited working memory.

Turing machines are not meant to be practical hardware designs. They are a powerful mathematical model used to define what an algorithm can compute.

Computability Terms

  • Decidable language: A Turing machine can always halt and correctly accept or reject every input.
  • Recognizable language: A Turing machine accepts every string in the language, but may run forever for some strings outside it.
  • Undecidable problem: No algorithm can correctly solve every possible input instance.

The Halting Problem

The halting problem asks whether a program will stop for a given input. Alan Turing proved that no general algorithm can answer this question correctly for every possible program and input. This result is important because it shows that some limits are fundamental, not merely limitations of current technology.

Chomsky Hierarchy

The Chomsky hierarchy organizes language classes from less powerful to more powerful. Each level can describe everything in the level below it, along with additional languages.

Type Language Class Typical Machine Example Use
Type 3 Regular Finite automaton Simple token and pattern recognition
Type 2 Context-free Pushdown automaton Balanced structures and programming syntax
Type 1 Context-sensitive Linear bounded automaton Languages requiring related counts or context
Type 0 Recursively enumerable Turing machine General computation

Regular Languages ⊂ Context-Free Languages ⊂ Context-Sensitive Languages ⊂ Recursively Enumerable Languages

How to Prepare TOC for Exams

  • Learn definitions, but also practise applying them to examples.
  • Draw state diagrams and transition tables for DFA and NFA questions.
  • For pumping-lemma proofs, clearly state the chosen string and why every possible split fails.
  • Practise converting regular expressions to finite automata and vice versa.
  • Keep the differences between regular, context-free, and decidable languages clear.

Frequently Asked Questions

Are DFA and NFA equally powerful?

Yes. Every NFA can be converted into an equivalent DFA, so both recognize exactly the regular languages.

Why can a PDA recognize balanced parentheses but a DFA cannot?

A PDA has a stack to remember an arbitrary number of opening parentheses. A DFA has only a fixed number of states and cannot keep track of an unlimited count.

Can the pumping lemma prove that a language is regular?

No. The pumping lemma is most useful for proving that a language is not regular. Passing its conditions is necessary for regular languages, but it is not sufficient proof of regularity.

What is the difference between decidable and recognizable languages?

A decider halts on every input. A recognizer must accept strings in the language, but it may never halt for strings outside the language.