Theory of Computation & Compilers
गणना सिद्धांत
Unit overview: the topics below, with their summaries, are the syllabus for this unit. The comprehensive note further down covers every topic in full — explanations, definitions, worked examples, tables, exam points and practice questions — and the short revision note after it is only a quick recap. Standalone one-topic learning pages are not built yet — every topic on this page is covered in the notes and the practice questions below, and each topic card links to those sections.
Premium chapters for this unit
Automata: DFA, NFA, PDA, TM → premium chapter · free preview · ~26 min · 4 practice questions
Compilers: parsing & code generation → premium chapter · free preview · ~26 min · 4 practice questions
Topics checklist — with weightage (platform estimate from past-question frequency, not an NTA guarantee)
Automata: DFA, NFA, PDA, TM
High weightageRegular vs context-free languages, pumping lemma.
Compilers: parsing & code generation
MediumLexical analysis, LL/LR parsing, intermediate code.
Comprehensive unit note · ~20 min read
Theory of computation asks what computers can do in principle, and compilers show how that theory is turned into working software. The two halves of this unit belong together: a compiler must recognise the tokens and sentence structures of a programming language, and the machines studied in automata theory define exactly which patterns can be recognised by finite memory, by a stack, or by an unbounded tape. When you understand why a finite automaton cannot count arbitrarily, you also understand why real languages need a stack for nested structures and why some problems have no algorithm at all. The automata half moves up a ladder of power. A deterministic finite automaton reads input once with finite memory and no choice. A nondeterministic finite automaton adds choice but, surprisingly, no extra power for regular languages. A pushdown automaton adds a stack and can handle nesting and matching, which is the realm of context-free languages. A Turing machine adds an unbounded tape and captures the general notion of computation itself, which then lets us prove limits: the halting problem has no general solution, and some languages are recognisable but not decidable. The Chomsky hierarchy organises these levels into regular, context-free, context-sensitive and recursively enumerable languages, each matched to a machine and a grammar type. The compiler half follows source code through phases. Lexical analysis groups characters into tokens, syntax analysis checks sentence structure against a grammar and builds a parse tree, semantic analysis checks types and scope, intermediate code generation produces a machine-independent form such as three-address code, optimisation improves that code without changing its meaning, and code generation produces target code. Parsing is where most examination marks lie: you must be able to compute FIRST and FOLLOW sets, build an LL(1) parsing table, explain why a grammar is or is not LL(1), and contrast top-down with bottom-up methods such as LR parsing. Study this unit by constructing small machines and tables by hand, because the procedures, not the definitions alone, are what examinations test.
Learning objectives
- Construct DFA and NFA for simple regular languages and convert NFA, including epsilon transitions, to equivalent DFA.
- Use regular expressions, the pumping lemma for regular languages, and context-free grammars to classify languages.
- Explain pushdown automata, ambiguity, and the pumping lemma for context-free languages.
- Distinguish decidable, recursively enumerable and non-recursively enumerable problems, including the halting problem.
- Name and explain the phases of compilation and the role of tokens, grammars and symbol tables.
- Compute FIRST and FOLLOW sets, build an LL(1) table, and compare LL(1) with LR parsing.
- Produce three-address intermediate code and explain basic code optimisation and syntax-directed translation.
Overview: Machines, Languages and Compilers at a Glance
A language is a set of strings over an alphabet, and a machine recognises a language by accepting exactly its strings. Changing the machine changes the class of languages it can recognise, and changing the grammar changes the class it can generate. This parallel between recognisers and generators is the backbone of the unit: finite automata match regular expressions and regular grammars, pushdown automata match context-free grammars, and Turing machines match unrestricted grammars. If a question asks whether a language belongs to a class, first ask what memory the recogniser would need: no counting beyond a fixed bound suggests regular, matching or nesting suggests context-free, and general computation suggests Turing power.
Compilers use the lower levels directly. Regular expressions describe tokens such as identifiers and numbers, so a lexical analyser is essentially a finite automaton. Context-free grammars describe statement structure such as nested blocks and expressions, so a parser is essentially a pushdown machine. Semantic rules and optimisation then go beyond pure syntax and need symbol tables and flow information. Keeping this map in mind prevents a common confusion: lexical analysis does not handle nesting, parsing does not check that a variable was declared, and optimisation does not change what a program computes, only how efficiently it computes it.
Automata: DFA, NFA, PDA, TM
A deterministic finite automaton, or DFA, is defined by a finite set of states, an input alphabet, a transition function that gives exactly one next state for each state and symbol, a start state, and a set of accepting states. It reads the input once from left to right and accepts if it ends in an accepting state. A nondeterministic finite automaton, or NFA, allows zero, one or several next states for a state and symbol, and also allows epsilon transitions that consume no input. An NFA accepts a string if at least one possible path ends in an accepting state. The subset construction converts an NFA to an equivalent DFA: each DFA state is the set of NFA states reachable on some path, the start state is the epsilon closure of the NFA start state, and a DFA state is accepting if it contains any NFA accepting state. The epsilon closure of a set of states is that set plus every state reachable by epsilon transitions alone. Although the construction can in principle produce exponentially many DFA states, in practice only reachable subsets are built, and many textbook conversions need only a handful.
Regular expressions describe the same languages as finite automata. The operators are union, concatenation and Kleene star, meaning zero or more repetitions, together with the empty string and the empty language. A language is regular if and only if some DFA, NFA or regular expression describes it. The pumping lemma for regular languages is the standard tool for proving non-regularity: if a language is regular, there is a pumping length p such that every string of length at least p can be split into three parts x, y and z, with y non-empty, the length of x plus y at most p, and x followed by any number of copies of y followed by z still in the language. To prove a language such as strings with equal numbers of two symbols is not regular, take a long string in the language, argue that y must lie inside the first block by the length condition, pump y, and show the pumped string breaks the equality. The argument only works if the chosen string and the use of the length bound are correct, which is why examiners reward careful choice of the witness string.
A context-free grammar has variables, terminals, a start variable and productions that replace a single variable by a string of variables and terminals. A derivation applies productions until only terminals remain, and the language is the set of terminal strings derivable from the start symbol. A grammar is ambiguous if some string has two different parse trees, or equivalently two different leftmost derivations, and ambiguity is a property of the grammar, not of the language, since an ambiguous grammar can sometimes be rewritten into an unambiguous one. The classic dangling-else and expression-precedence examples show why grammars for real languages are carefully designed with precedence and associativity rules. A pushdown automaton adds a stack to a finite control: it can push and pop symbols while reading input, so it can match opening and closing symbols and recognise nested structures that no finite automaton can handle. A language is context-free if and only if some pushdown automaton recognises it, under the usual acceptance by final state or by empty stack. The pumping lemma for context-free languages is similar in spirit but pumps two substrings at once, reflecting the stack-based nesting, and it proves languages requiring three-way equality or cross-serial matching are not context-free.
A Turing machine has a finite control and an unbounded tape with a read and write head that moves left or right. Variants such as multiple tapes, nondeterminism or a two-way infinite tape do not change the class of computable functions, though they may change efficiency. A language is recursive, or decidable, if some Turing machine halts with an accept or reject answer on every input. It is recursively enumerable if some machine accepts strings in the language but may loop forever on strings outside it. The halting problem asks whether a given machine halts on a given input, and it is undecidable: assuming a decider exists leads to a machine that halts exactly when the decider says it does not, a contradiction. The complement of a decidable language is decidable, and a language is decidable if and only if both it and its complement are recursively enumerable. The Chomsky hierarchy places regular languages inside context-free languages, inside context-sensitive languages, inside recursively enumerable languages, with each inclusion strict. Regular grammars have productions of restricted form, context-free grammars replace one variable at a time, context-sensitive grammars never shorten a sentential form, and unrestricted grammars correspond to Turing machines.
Compilers: parsing & code generation
Compilation proceeds in phases, each transforming one representation into the next. Lexical analysis scans characters and groups them into tokens such as keywords, identifiers, numbers, operators and punctuation, discarding whitespace and comments and reporting illegal characters. Each token carries a type and often an attribute such as the lexeme or a symbol-table pointer. Syntax analysis, or parsing, checks the token sequence against the grammar and builds a parse tree or syntax tree. Semantic analysis checks scope, declarations and types, and annotates the tree. Intermediate code generation produces a machine-independent form, optimisation improves it, and code generation emits target code with register allocation and instruction selection. A symbol table stores identifiers with their type, scope and storage information, and it must support nested scopes, so entering a block pushes a scope and leaving it restores the previous one. Errors can be reported in any phase, but a lexical error is about characters, a syntax error about structure, and a semantic error about meaning or types.
Parsing divides into top-down and bottom-up methods. Top-down parsing builds the parse tree from the root down, expanding the leftmost variable at each step, as in recursive descent and LL(1) parsing. LL(1) means scanning left to right, deriving a leftmost derivation, with one symbol of lookahead. To build an LL(1) table, compute FIRST sets, the terminals that can begin a string derived from a symbol, and FOLLOW sets, the terminals that can follow a symbol in some derivation, plus the end marker. A production A derives alpha is entered in the table row for A and column a for every terminal a in FIRST of alpha, and if alpha can derive the empty string, also for every terminal in FOLLOW of A. A grammar is LL(1) if its table has no multiply defined entry, which fails when FIRST sets of alternatives overlap or when a nullable alternative collides with the FOLLOW set. Left recursion, where a variable derives itself as its first symbol, breaks top-down parsing by causing infinite expansion, so it must be removed, and common prefixes must be factored so that lookahead can choose between alternatives.
Bottom-up parsing builds the tree from the leaves up by shifting tokens onto a stack and reducing a handle on the stack top to a variable when it matches a production right-hand side. LR parsing, including SLR, LALR and canonical LR, scans left to right with rightmost derivation in reverse and is more powerful than LL(1): it handles left recursion and a larger class of grammars, at the cost of larger tables built from sets of LR items. An LR item is a production with a dot marking how much of the right-hand side has been seen, and closure and goto operations build the automaton of item sets. Shift-reduce and reduce-reduce conflicts show that a grammar is not in the corresponding LR class. Syntax-directed translation attaches semantic actions or attributes to productions, so translation or checking happens during parsing: synthesised attributes flow from children to parent, as in computing an expression value, while inherited attributes flow from parent or siblings, as in passing a declaration type to identifiers in a list.
Intermediate code is often three-address code, where each instruction has at most one operator and at most three addresses, such as t1 equals a plus b, and t2 equals t1 times c. Temporaries hold intermediate values, and jumps and labels express control flow. For the assignment x equals a plus b times c, respecting precedence, the code is t1 equals b times c, then x equals a plus t1. Code optimisation must preserve meaning while improving speed or size. Common techniques include constant folding, which evaluates constant expressions at compile time, dead-code elimination, which removes code whose results are never used, common-subexpression elimination, which reuses a previously computed value, copy propagation, and loop-invariant code motion, which moves computations out of loops when they do not change inside the loop. A basic block is a maximal straight-line sequence with one entry and one exit, and much local optimisation works within a block, while global optimisation works across blocks using flow analysis. Peephole optimisation makes small local replacements in the target code, such as removing redundant loads.
Key definitions
- Alphabet: A finite non-empty set of symbols from which strings are formed.
- DFA: A deterministic finite automaton with exactly one transition for each state and input symbol, reading input once from left to right.
- NFA: A nondeterministic finite automaton allowing zero, one or several transitions for a state and symbol, plus epsilon transitions.
- Epsilon closure: A set of states plus every state reachable from it by epsilon transitions alone.
- Regular expression: An expression built from union, concatenation and Kleene star that denotes a regular language.
- Context-free grammar: A grammar whose productions replace a single variable by a string of variables and terminals.
- Ambiguous grammar: A grammar in which some string has two different parse trees or two different leftmost derivations.
- Pushdown automaton: A finite automaton equipped with a stack, capable of recognising context-free languages.
- Turing machine: A finite control with an unbounded read and write tape, taken as the standard model of general computation.
- Decidable language: A language for which some Turing machine halts with an accept or reject answer on every input.
- Recursively enumerable language: A language accepted by some Turing machine that may loop forever on inputs outside the language.
- Token: A unit produced by lexical analysis, such as a keyword, identifier, number or operator, with a type and attributes.
- FIRST set: For a symbol, the set of terminals that can begin a string derived from that symbol, plus the empty string if applicable.
- FOLLOW set: For a variable, the set of terminals that can immediately follow it in some derivation, plus the end marker for the start symbol.
- LL(1) parsing: Top-down parsing scanning left to right with leftmost derivation and one symbol of lookahead.
- LR parsing: Bottom-up parsing scanning left to right with rightmost derivation in reverse, using shift and reduce actions.
- Syntax-directed translation: Translation or checking performed by semantic actions and attributes attached to grammar productions.
- Three-address code: Intermediate code in which each instruction has at most one operator and at most three addresses.
- Symbol table: A table mapping identifiers to information such as type, scope and storage, supporting nested scopes.
- Basic block: A maximal straight-line sequence of instructions with a single entry point and a single exit point.
Formulas
- Subset construction bound: an NFA with n states converts to a DFA with at most 2 to the power n states.
- Regular closure: regular languages are closed under union, concatenation, Kleene star, complement and intersection.
- Pumping length condition: for a regular language there is p such that every string w of length at least p splits as xyz with y non-empty, length of xy at most p, and x times y to the power k times z in the language for all k at least 0.
- FIRST rule: FIRST of a sequence is built left to right, adding FIRST of each symbol and continuing past a symbol only if it can derive the empty string.
- FOLLOW rule: if A derives alpha B beta, then FIRST of beta excluding empty goes into FOLLOW of B, and if beta can derive empty, FOLLOW of A goes into FOLLOW of B.
Worked examples
Example 1: Convert this NFA to a DFA by subset construction. States q0, q1, q2; start q0; accepting q2. Transitions: q0 on a goes to q0 and q1; q0 on b goes to q0; q1 on b goes to q2; no other transitions, no epsilon transitions. Build only reachable DFA states.
Start state is the set containing q0, written as {q0}. On a, q0 goes to q0 and q1, so the next state is {q0, q1}. On b, q0 goes to q0, so the next state is {q0}. Now process {q0, q1}. On a, q0 contributes q0 and q1 while q1 contributes nothing, giving {q0, q1} again. On b, q0 contributes q0 and q1 contributes q2, giving {q0, q2}. Process {q0, q2}. On a, q0 contributes q0 and q1, giving {q0, q1}. On b, q0 contributes q0, giving {q0}. The reachable DFA states are {q0}, {q0, q1} and {q0, q2}. A DFA state is accepting if it contains q2, so only {q0, q2} is accepting. The DFA has 3 states, far fewer than the bound of 2 to the power 3 equals 8.
Example 2: Compute FIRST and FOLLOW for the grammar: S derives A B, A derives a A or empty, B derives b B or empty. Include the end marker in FOLLOW of S.
FIRST of A: from a A comes a, and from empty comes empty, so FIRST(A) equals {a, empty}. FIRST of B: from b B comes b, and from empty comes empty, so FIRST(B) equals {b, empty}. FIRST of S: from A B, take FIRST(A) without empty, giving a, then since A can be empty take FIRST(B) without empty, giving b, then since B can also be empty add empty, so FIRST(S) equals {a, b, empty}. FOLLOW of S equals {end marker}, by the start-symbol rule. For A in S derives A B: FOLLOW(A) gets FIRST(B) without empty, which is b, and since B can be empty it also gets FOLLOW(S), which is the end marker, so FOLLOW(A) equals {b, end marker}. For B in S derives A B: FOLLOW(B) gets FOLLOW(S), which is the end marker, so FOLLOW(B) equals {end marker}. Check: A is followed by b when B produces b, or by end when B is empty.
Example 3: Give three-address code for x equals a plus b times c, and for if a is less than b then x equals 1 else x equals 2, respecting precedence.
For x equals a plus b times c, multiplication binds tighter than addition, so compute the product first: t1 equals b times c, then x equals a plus t1. For the conditional, compare first and jump: if a is less than b then goto L1, else goto L2. Label L1: x equals 1, then goto L3. Label L2: x equals 2. Label L3: the code after the statement. Each instruction has at most one operator, temporaries hold intermediate results, and labels express the two branches and the join point.
Example 4: Use the pumping lemma to show that the language of strings a to the power n followed by b to the power n, for n at least 0, is not regular.
Assume the language is regular with pumping length p. Choose w equals a to the power p followed by b to the power p, which is in the language and has length 2p, at least p. Any split xyz with length of xy at most p and y non-empty forces y to lie entirely inside the initial a block, since the first p symbols are all a. Pumping y twice, for k equals 2, gives more a symbols than b symbols, because the a count becomes p plus length of y while the b count stays p. That pumped string is not in the language, contradicting the pumping lemma. Hence the assumption is false and the language is not regular. It is context-free, since a pushdown automaton can push one symbol per a and pop one per b.
DFA versus NFA versus PDA versus TM
| Machine | Memory | Language class | Key point |
|---|---|---|---|
| DFA | Finite states only | Regular | Exactly one transition per state and symbol |
| NFA | Finite states, with choice | Regular | Same power as DFA, via subset construction |
| PDA | Finite states plus a stack | Context-free | Can match nesting and balanced symbols |
| Turing machine | Finite states plus unbounded tape | Recursively enumerable | General model of computation; halting undecidable |
LL versus LR parsing
| Property | LL(1) | LR |
|---|---|---|
| Direction | Top-down, root to leaves | Bottom-up, leaves to root |
| Derivation | Leftmost | Rightmost in reverse |
| Left recursion | Not allowed, must be removed | Allowed |
| Power | Smaller grammar class | Larger grammar class |
| Table size | Smaller | Larger, especially canonical LR |
Compiler phases
| Phase | Input | Output |
|---|---|---|
| Lexical analysis | Characters | Tokens |
| Syntax analysis | Tokens | Parse or syntax tree |
| Semantic analysis | Syntax tree | Annotated tree, checked types and scope |
| Intermediate code generation | Annotated tree | Three-address code |
| Optimisation | Intermediate code | Improved intermediate code |
| Code generation | Intermediate code | Target code |
Chomsky hierarchy
| Level | Grammar | Machine |
|---|---|---|
| Type 3 | Regular | Finite automaton |
| Type 2 | Context-free | Pushdown automaton |
| Type 1 | Context-sensitive | Linear bounded automaton |
| Type 0 | Unrestricted | Turing machine |
Diagrams (described)
Subset construction diagram: NFA states drawn as circles with arrows, beside a DFA whose states are drawn as boxes labelled by sets of NFA states, with arrows showing how each input symbol maps one set to another.
Parse tree diagram: a syntax tree for an expression with operators at internal nodes and operands at leaves, showing how precedence places multiplication below addition in the tree.
LL(1) table diagram: a grid with variables as rows and terminals plus end marker as columns, each filled cell holding the production to apply, and empty cells signalling a syntax error.
Pushdown automaton diagram: a finite control box beside a stack drawn as a vertical column, with an arrow pushing a symbol when an opening symbol is read and popping it when the matching closing symbol is read.
Compiler pipeline diagram: a left-to-right chain of boxes for lexical analysis, syntax analysis, semantic analysis, intermediate code, optimisation and code generation, with the symbol table drawn as a side box connected to every phase.
Exam points
- NFA and DFA recognise exactly the same class of languages: the regular languages. Nondeterminism adds convenience, not power, at this level.
- Epsilon closure is essential in subset construction: the DFA start state is the epsilon closure of the NFA start state, not the start state alone.
- The pumping lemma proves non-regularity; it can never prove a language is regular, since regular languages satisfy it but so might others in a particular test.
- Ambiguity is a property of a grammar: a language can have both an ambiguous and an unambiguous grammar.
- A pushdown automaton can recognise balanced parentheses and equal numbers of two symbols, which no finite automaton can.
- The halting problem is undecidable, and the complement of a recursively enumerable language need not be recursively enumerable.
- FIRST and FOLLOW sets drive LL(1) table construction; a multiply defined table entry means the grammar is not LL(1).
- Left recursion must be removed for top-down parsing but is acceptable for LR parsing.
- Three-address code has at most one operator per instruction, and temporaries hold intermediate values.
- Lexical analysis produces tokens, parsing checks structure, and semantic analysis checks types and scope: do not assign one phase work belonging to another.
Common mistakes
- Mistake: claiming an NFA is more powerful than a DFA. Correction: subset construction shows they recognise the same regular languages.
- Mistake: using the pumping lemma to prove regularity. Correction: the lemma gives a necessary condition for regularity, so it can only disprove regularity by contradiction.
- Mistake: forgetting epsilon closure in NFA to DFA conversion. Correction: always close under epsilon transitions before and after each input symbol.
- Mistake: calling a language ambiguous. Correction: ambiguity belongs to a grammar; a language is ambiguous only if every grammar for it is ambiguous.
- Mistake: putting FIRST of the whole right-hand side into FOLLOW. Correction: FOLLOW is computed from what follows a variable in productions, using FIRST of the following part and FOLLOW of the left-hand side when needed.
- Mistake: trying LL(1) parsing on a left-recursive grammar without removing left recursion. Correction: eliminate left recursion and left-factor common prefixes first.
- Mistake: thinking optimisation changes program meaning. Correction: valid optimisation preserves meaning and only improves time, space or code size.
- Mistake: assuming every recursively enumerable language is decidable. Correction: recursively enumerable allows looping on non-members; decidable requires halting on all inputs.
Practice questions from this note (original practice — not official PYQs)
Checking login…
Quick revision: Automata ladder first: DFA and NFA both give regular languages, with subset construction using epsilon closure and at most 2 to the power n DFA states; regular expressions use union, concatenation and Kleene star; the pumping lemma disproves regularity by pumping inside the first block. Context-free next: grammars replace one variable at a time, ambiguity belongs to a grammar and means two parse trees, pushdown automata add a stack for nesting, and the context-free pumping lemma pumps two parts at once. Turing next: decidable means halting on all inputs, recursively enumerable allows looping on non-members, halting is undecidable, and the hierarchy runs regular inside context-free inside context-sensitive inside recursively enumerable. Compilers last: lexical analysis makes tokens, syntax analysis makes trees, semantic analysis checks types and scope, and symbol tables handle nested scopes. For LL(1), compute FIRST as what can begin a derivation and FOLLOW as what can follow a variable, fill the table from FIRST of the right-hand side plus FOLLOW when nullable, and treat a multiply defined entry as not LL(1); LR is bottom-up, handles left recursion, and uses shift and reduce. Three-address code allows one operator per instruction, and constant folding, dead-code elimination, common-subexpression elimination and loop-invariant motion preserve meaning while improving code.
Unit revision note (quick recap)
Theory asks what can be computed and with what machine. Compilers turn that theory into practice: source text → tokens → tree → code.
Learning objectives
- Classify languages by machine
- Explain parsing and compiler phases
- Use the pumping lemma idea
Key concepts
- Regular language: Accepted by a DFA/NFA; described by a regular expression.
- Context-free language: Accepted by a pushdown automaton; described by a context-free grammar.
- Context-sensitive language: Accepted by a linear-bounded automaton.
- Lexical vs syntax analysis: Lexer produces tokens; parser builds the parse tree from tokens.
- LL vs LR: LL parses top-down, left-to-right; LR parses bottom-up and handles more grammars.
Worked examples
- aⁿbⁿ is context-free (needs a stack to count) but not regular (a DFA cannot count unboundedly).
Exam points
- Regular ↔ DFA, CFL ↔ PDA, CSL ↔ LBA, recursively enumerable ↔ Turing machine.
- Compiler order: lexical → syntax → semantic → intermediate code → optimisation → code generation.
Common mistakes
- Saying a PDA accepts regular languages only — it accepts context-free languages, which include regular ones.
Quick revision: Automata hierarchy, grammars, parsing, code generation, compiler phases.
Practice questions from the whole unit bank (33 in the bank)
This unit's practice bank — the note above has its own smaller practice set drawn from the same bank, so a question can appear in both lists. The list below shows the free sample or the full bank depending on your plan.
Checking login…
Related tests
Unit test for this unit (33 bank questions, 40 min) · Full Mock — CS Paper 2 (100 questions) · Combined 150-question mock (180 min). All +2 per correct, no negative marking.
Revision summary
Automata hierarchy, grammars, parsing, code generation, compiler phases.
After revising, take the unit test above, then check your unit-wise report on the Dashboard to find weak topics.