How to study Theory of Computation — Semester IV, Pokhara University BECE
What it covers
Theory of automata, formal languages and computation: finite automata, regular expressions, context-free grammars, pushdown automata, Turing machines, decidability and computational complexity.
Topics worth extra time
- Finite automata: DFA, NFA and converting between them
- Regular expressions and the pumping lemma for regular languages
- Context-free grammars, derivations, parse trees and normal forms
- Pushdown automata
- Turing machines, decidability and undecidability
How to study it
Design machines yourself for many small languages ("strings ending in 01", "equal numbers of a and b"). Test each design with accepted and rejected strings. For proofs like the pumping lemma, learn the structure of the argument and practise it on different languages.
In the exam
Draw state diagrams clearly with start and accepting states marked, and include a transition table where asked. Show conversions (NFA to DFA, grammar to normal form) step by step.