Theory of Computation Exam Practice

This lesson consolidates the key topics from the Theory of Computation unit and provides exam-style guidance. Use this to review the major concepts, practise applying them, and prepare for the types of questions that appear in A-Level Computer Science exams.

---

Topic Summary

Topic	Key Concepts
Abstraction & Automation	Removing unnecessary detail; modelling problems for computation
Finite State Machines	States, transitions, DFA, NFA, regular languages, state diagrams and tables
Regular Expressions	Concatenation, alternation (|), Kleene star (*), equivalence with FSMs
Context-Free Languages & BNF	Production rules, non-terminals, terminals, parse trees, Chomsky hierarchy
RPN & Parsing	Infix to postfix conversion, stack-based evaluation, shunting-yard algorithm
Turing Machines	Tape, head, states, transition function, Church-Turing thesis, UTM
Halting Problem	Undecidability, proof by contradiction, implications
Algorithm Classification	P, NP, NP-complete, tractable, intractable, computable, heuristics
Limits of Computation	Theoretical, practical, and physical limits

---

Common Exam Question Types

1. FSM Design and Tracing

Typical question: "Draw an FSM that accepts all binary strings containing an odd number of 1s."

Approach:

• Identify what information the states need to track (odd/even count of 1s).
• Draw the states and transitions.
• Label the start state and accepting state(s).
• Test with example strings.

Answer:

States: {Even, Odd}. Start: Even. Accepting: {Odd}.

State	Input 0	Input 1
Even	Even	Odd
Odd	Odd	Even

Test: "110" → Even → Odd → Even → Even. Rejected (even number of 1s). ✓ Test: "101" → Even → Odd → Odd → Even → ... wait: "101" has two 1s (even). Let's re-trace: Even →(1)→ Odd →(0)→ Odd →(1)→ Even. Rejected. ✓ Test: "1" → Even →(1)→ Odd. Accepted. ✓

---

2. Regular Expression Writing

Typical question: "Write a regular expression for all binary strings that start with 1 and end with 0."

Approach:

• The string must start with 1: first character is 1.
• The string must end with 0: last character is 0.
• In between: any number of 0s and 1s.

Answer: 1(0|1)*0

Check: "10" ✓, "100" ✓, "1110" ✓, "0110" ✗ (doesn't start with 1). Minimum length string: "10".

---

3. BNF Grammar Writing

Typical question: "Write a BNF grammar for a valid variable name that starts with a letter and is followed by zero or more letters or digits."

Answer:

<variable>  ::= <letter> <rest>
<rest>      ::= <letter> <rest> | <digit> <rest> | ε
<letter>    ::= a | b | c | ... | z | A | B | ... | Z
<digit>     ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

---

4. Infix to RPN Conversion

Typical question: "Convert the expression (A + B) × C − D to Reverse Polish Notation."

Approach: Build the parse tree or use the shunting-yard algorithm.

Parse tree:

        −
       / \
      ×   D
     / \
    +   C
   / \
  A   B

Post-order traversal: A B + C × D −

Answer: A B + C × D −

---

5. RPN Evaluation

Typical question: "Evaluate the RPN expression 6 3 2 × + 4 −"