Questions
4 questions per paper
Difficulty
Medium
Importance
Medium yield; focus on standard algorithms
Overview
Theory of Computation and Compiler Design forms the backbone of computer science theory, exploring what computers can compute and how programming languages are translated into machine code. For PSU exams, this topic is critical as it tests your ability to identify language classes and trace parsing steps, which are frequently featured in technical segments.
Finite Automata and Regular Languages
This section focuses on the hierarchy of languages and the recognition of patterns using state machines. Understanding the distinction between Deterministic (DFA) and Non-deterministic (NFA) finite automata is essential for solving state reduction and language classification problems.
- Pumping Lemma for Regular Languages
- Myhill-Nerode Theorem
- DFA to Regular Expression conversion
- Closure properties: Union, Intersection, Complement
- Moore and Mealy machine definitions
Context-Free Grammars and Parsing
Context-Free Grammars (CFG) describe the structure of programming languages. In PSU exams, you must know how to identify grammar ambiguity and differentiate between top-down (LL) and bottom-up (LR) parsing strategies.
- Chomsky Hierarchy levels
- Removing Left Recursion and Left Factoring
- FIRST and FOLLOW sets calculation
- LL(1) parsing table construction
- LR(0), SLR, LALR, and CLR parser hierarchy
Turing Machines and Decidability
Turing Machines represent the most powerful computational model. Questions here typically revolve around the decidability of problems and the characteristics of Recursively Enumerable languages.
- Halting Problem is undecidable
- Rice's Theorem
- Post Correspondence Problem (PCP)
- Church-Turing Thesis
- Universal Turing Machine concept
Compiler Design and Optimization
This area covers the transformation of source code into executable form through various phases. Focus on the functionality of the lexical analyzer and the logic behind code optimization techniques used to improve runtime performance.
- Phases of a compiler: Lexical, Syntax, Semantic, IR, Code Gen
- Symbol Table organization
- Dead code elimination
- Loop unrolling and constant folding
- Three-address code representation
Formula Sheet
Pumping Lemma: |w| >= p
Number of states in DFA = 2^n
FIRST(A) = {a | A ->* a...}
FOLLOW(A) = {a | S ->* ...Aa...}
Exam Tip
Focus on calculating FIRST and FOLLOW sets accurately, as these are the most common source of easy marks in parsing questions.
Common Mistakes
- Confusing the subset relationship between language classes (e.g., assuming all regular languages are not context-free).
- Miscalculating the FOLLOW set by ignoring the presence of Epsilon productions.
- Forgetting that non-deterministic pushdown automata are more powerful than deterministic ones, unlike finite automata.
More Revision Notes
Ready to test yourself?
Play topic-wise Theory of Computation & Compiler Design questions in Aspirant Arcade — gamified MCQ practice.
Download Free