UGC NET Computer Science Theory of Computation and Compilers Syllabus

Theory of Computation and Compilers syllabus — full chapter and topic list

Expand any chapter to see its topics and sub-topics. This is the whole examinable outline for Theory of Computation and Compilers in UGC NET Computer Science, not a summary of it.

1. 1

   Theory of Computation

   4 topics

   • Formal Language
   • Non-Computational Problems
   • Diagonal Argument
   • Russel's Paradox
2. 2

   Regular Language Models

   10 topics

   • Deterministic Finite Automaton (DFA)
   • Non-Deterministic Finite Automaton (NDFA)
   • Equivalence of DFA and NDFA
   • Regular Languages
   • Regular Grammars
   • Regular Expressions
   • Properties of Regular Language
   • Pumping Lemma
   • Non-Regular Languages
   • Lexical Analysis
3. 3

   Context Free Language

   9 topics

   • Pushdown Automaton (PDA)
   • Non-Deterministic Pushdown Automaton (NPDA)
   • Context Free Grammar
   • Chomsky Normal Form
   • Greibach Normal Form
   • Ambiguity
   • Parse Tree Representation of Derivation Trees
   • Equivalence of PDA’s and Context Free Grammars
   • Properties of Context Free Language
4. 4

   Turing Machines (TM)

   8 topics

   • Standard Turing Machine and its Variations
   • Universal Turing Machines
   • Models of Computation and Church-Turing Thesis
   • Recursive and Recursively-Enumerable Languages
   • Context-Sensitive Languages
   • Unrestricted Grammars
   • Chomsky Hierarchy of Languages
   • Construction of TM for Simple Problems
5. 5

   Unsolvable Problems and Computational Complexity

   6 topics

   • Unsolvable Problem
   • Halting Problem
   • Post Correspondence Problem
   • Unsolvable Problems for Context-Free Languages
   • Measuring and Classifying Complexity
   • Tractable and Intractable Problems
6. 6

   Syntax Analysis

   9 topics

   • Associativity
   • Precedence
   • Grammar Transformations
   • Top Down Parsing
   • Recursive Descent Predictive Parsing
   • LL(1) Parsing
   • Bottom up Parsing
   • LR Parser
   • LALR(1) Parser
7. 7

   Semantic Analysis

   7 topics

   • Attribute Grammar
   • Syntax Directed Definitions
   • Inherited and Synthesized Attributes
   • Dependency Graph
   • Evaluation Order
   • S-attributed and L-attributed Definitions
   • Type-Checking
8. 8

   Run Time System

   6 topics

   • Storage Organization
   • Activation Tree
   • Activation Record
   • Stack Allocation of Activation Records
   • Parameter Passing Mechanisms
   • Symbol Table
9. 9

   Intermediate Code Generation

   6 topics

   • Intermediate Representations
   • Translation of Declarations
   • Assignments
   • Control Flow
   • Boolean Expressions
   • Procedure Calls
10. 10

    Code Generation and Code Optimization

    7 topics

    • Control-flow Analysis
    • Data-flow Analysis
    • Local Optimization
    • Global Optimization
    • Loop Optimization
    • Peep-Hole Optimization
    • Instruction Scheduling

Theory of Computation and Compilers flashcards for UGC NET Computer Science

23 of 70 cards from the Theory of Computation and Compilers deck — real questions with worked answers.

1. What formally defines a Deterministic Finite Automaton (DFA)?

   A 5-tuple (Q, Σ, δ, q0, F) where Q is a finite set of states, Σ the input alphabet, δ: Q×Σ→Q the transition function, q0 the start state, and F⊆Q the set of accepting states. For each state-symbol pair there is exactly one next state.

2. How does a Non-Deterministic Finite Automaton (NDFA/NFA) differ from a DFA in its transition function?

   In an NFA the transition function maps to a set of states: δ: Q×(Σ∪{ε})→2^Q. It allows multiple (or zero) next states and ε-transitions, whereas a DFA has exactly one next state per input symbol.

3. State the equivalence result between DFA and NFA, and the size relationship via subset construction.

   DFAs and NFAs recognize exactly the same class of languages (regular languages). Any NFA with n states can be converted to an equivalent DFA with up to 2^n states using the subset (powerset) construction.

4. What is a Regular Language?

   A language that can be accepted by some finite automaton (DFA or NFA), equivalently described by a regular expression or generated by a regular (Type-3) grammar.

5. What form do productions take in a (right-linear) Regular Grammar?

   Each production is of the form A → aB or A → a (or A → ε), where A,B are non-terminals and a is a terminal. In left-linear grammars the non-terminal appears on the left: A → Ba or A → a.

6. List the three basic operations of Regular Expressions and their precedence order.

   Union (+ or |), concatenation, and Kleene star (*). Precedence from highest to lowest: star (closure) > concatenation > union. Parentheses override precedence.

7. Which closure properties hold for Regular Languages?

   Regular languages are closed under union, concatenation, Kleene star, intersection, complement, difference, reversal, and homomorphism. The class is a Boolean algebra (closed under all set operations).

8. State the Pumping Lemma for Regular Languages.

   For every regular language L there exists a pumping length p such that any string w∈L with |w|≥p can be written as w=xyz where |xy|≤p, |y|≥1, and xy^i z∈L for all i≥0.

9. How is the Pumping Lemma used to prove a language is non-regular?

   By contradiction: assume L is regular with pumping length p, pick a specific string w∈L with |w|≥p, then show that for every valid decomposition w=xyz some pumped string xy^i z falls outside L, contradicting the lemma.

10. Give a classic example of a Non-Regular Language and why no DFA accepts it.

    L={a^n b^n | n≥0} is non-regular because a finite automaton has finitely many states and cannot count an unbounded number of a's to match an equal number of b's; the Pumping Lemma confirms this.

11. What is the role of Lexical Analysis in a compiler?

    The lexical analyzer (scanner) reads the source character stream and groups characters into tokens (lexemes with token types), removes whitespace/comments, and feeds tokens to the parser. Tokens are typically specified by regular expressions and recognized by finite automata.

12. What formally defines a Pushdown Automaton (PDA)?

    A 7-tuple (Q, Σ, Γ, δ, q0, Z0, F): states Q, input alphabet Σ, stack alphabet Γ, transition δ, start state q0, initial stack symbol Z0, and accepting states F. It is a finite automaton augmented with a stack.

13. How does the power of a Non-Deterministic PDA (NPDA) compare to a Deterministic PDA (DPDA)?

    NPDAs are strictly more powerful: they accept exactly the context-free languages, while DPDAs accept only the deterministic context-free languages, a proper subset. (For finite automata, determinism makes no difference, but for PDAs it does.)

14. What is a Context-Free Grammar (CFG)?

    A 4-tuple (V, T, P, S): variables V, terminals T, productions P of the form A→α with A a single variable and α∈(V∪T)*, and start symbol S. CFGs generate exactly the context-free languages.

15. What are the production restrictions of Chomsky Normal Form (CNF)?

    Every production is of the form A→BC (two variables) or A→a (a single terminal); the only allowed ε-production is S→ε if ε is in the language, and S must not appear on any right-hand side.

16. What is the production form required by Greibach Normal Form (GNF)?

    Every production is of the form A→aα where a is a single terminal and α is a (possibly empty) string of variables. GNF guarantees each derivation step produces exactly one terminal.

17. What does it mean for a Context-Free Grammar to be ambiguous?

    A grammar is ambiguous if some string in its language has more than one distinct parse (derivation) tree, equivalently more than one leftmost (or rightmost) derivation.

18. What is a Parse Tree (derivation tree) and what does its yield represent?

    A parse tree is an ordered tree whose root is the start symbol, internal nodes are variables, and leaves are terminals or ε; it graphically depicts a derivation. Its yield (left-to-right concatenation of leaves) is the derived terminal string.

19. State the equivalence between PDAs and Context-Free Grammars.

    A language is context-free if and only if it is accepted by some pushdown automaton. Every CFG can be converted to an equivalent PDA and every PDA to an equivalent CFG.

20. Which closure properties hold (and fail) for Context-Free Languages?

    CFLs are closed under union, concatenation, Kleene star, homomorphism, and reversal, but NOT closed under intersection or complement. (Intersection of a CFL with a regular language is, however, context-free.)

21. What defines a standard Turing Machine?

    A 7-tuple (Q, Σ, Γ, δ, q0, B, F) with a semi-infinite/infinite tape, tape alphabet Γ (including blank B), transition δ: Q×Γ→Q×Γ×{L,R} that writes a symbol and moves the head left or right. It is the standard model of effective computation.

22. Name common Turing Machine variations and state their computational power.

    Multi-tape, multi-track, non-deterministic, two-way infinite tape, and multi-dimensional Turing machines. All are equivalent in power to the standard single-tape deterministic TM (they recognize exactly the recursively enumerable languages).

23. What is a Universal Turing Machine (UTM)?

    A Turing machine U that takes as input an encoding of an arbitrary TM M and an input w, and simulates M on w. It demonstrates that a single machine can compute any computable function—the theoretical basis of the stored-program computer.

See more Theory of Computation and Compilers flashcards →

Planning Theory of Computation and Compilers for UGC NET Computer Science

Theory of Computation and Compilers (UGC NET Computer Science) FAQ