Introduction
Theory of Computation is the branch of computer science that asks two big questions: What can be computed? and How do we describe patterns and languages precisely? It gives us the mathematical machines and grammars behind compilers, search engines, text-matching (regex), and the very definition of an "algorithm."
For BCS, Bank IT, and IT-officer exams this topic is a reliable source of MCQs: regular expressions, DFA/NFA, the pumping lemma, context-free grammars, pushdown automata, the Chomsky hierarchy, and the Turing machine. The questions are conceptual and rarely need heavy calculation, so a clear mental model wins marks fast.
Learning objectives
- Define alphabet, string, and language precisely.
- Read and write regular expressions for given patterns.
- Draw and trace DFA and NFA state diagrams; explain NFA-to-DFA conversion.
- Use the pumping lemma to prove a language is not regular.
- Build context-free grammars, derivations, and parse trees; spot ambiguity.
- Explain the pushdown automaton and the Turing machine at a concept level.
- Place every language class in the Chomsky hierarchy (Type 0–3).
- Perform left-recursion elimination on a grammar.