UGC NET Computer Science Theory of Computation and Compilers Syllabus

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.

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).

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.

State the Church-Turing Thesis.

Any function that is effectively (algorithmically) computable can be computed by a Turing machine. It equates the intuitive notion of an algorithm with TM computability; it is a thesis (not a provable theorem).

Distinguish Recursive from Recursively Enumerable languages.

A recursive (decidable) language has a TM that halts on every input, accepting or rejecting (a total decider). A recursively enumerable (r.e.) language has a TM that halts and accepts strings in the language but may loop forever on strings not in it. Recursive ⊊ r.e.

What characterizes Context-Sensitive Languages and the grammars/automata for them?

They are generated by context-sensitive (Type-1) grammars with non-contracting productions α→β where |α|≤|β| (allowing S→ε if S unused on RHS), and accepted by Linear Bounded Automata (LBAs)—TMs whose tape is bounded by the input length.

What are Unrestricted (Type-0) Grammars and what languages do they generate?

Grammars whose productions α→β have α containing at least one variable with no other restriction. They generate exactly the recursively enumerable languages and are equivalent in power to Turing machines.

State the Chomsky Hierarchy of grammars, languages, and their machines.

Type-0: unrestricted → recursively enumerable → Turing machine. Type-1: context-sensitive → CSL → linear bounded automaton. Type-2: context-free → CFL → pushdown automaton. Type-3: regular → regular language → finite automaton. Each class properly contains the next.

What is the Halting Problem and what is its decidability status?

The Halting Problem asks whether an arbitrary TM M halts on input w. It is undecidable—no algorithm can decide it for all (M,w)—though it is recursively enumerable (semi-decidable).

What is a Diagonalization (Diagonal) Argument used to prove?

A technique (Cantor's) that constructs an object differing from every item in an enumeration along the diagonal. It proves the reals are uncountable and, in computability, that the set of languages is uncountable while TMs are countable—so some languages are not recursively enumerable, and that the Halting Problem is undecidable.

What is Russell's Paradox and its significance?

Consider the set R of all sets that do not contain themselves; asking whether R∈R yields a contradiction either way. It exposed inconsistency in naive set theory, motivating axiomatic set theory and highlighting limits of self-reference relevant to undecidability.

What is the Post Correspondence Problem (PCP)?

Given two lists of strings A=(a1,…,an) and B=(b1,…,bn), decide whether there is a sequence of indices i1…ik such that a_{i1}…a_{ik}=b_{i1}…b_{ik}. PCP is undecidable and is widely used to prove other undecidability results.

Name two undecidable problems for Context-Free Grammars/Languages.

Undecidable for CFGs: whether a grammar is ambiguous, whether two CFGs generate the same language (equivalence), whether L(G1)∩L(G2)=∅, whether a CFL equals Σ*, and whether a CFL is regular. (Membership and emptiness, however, ARE decidable.)

What is the difference between Tractable and Intractable problems?

Tractable problems are solvable in polynomial time (class P). Intractable problems require super-polynomial (e.g., exponential) time in the worst case; NP-complete problems are believed intractable since no polynomial algorithm is known (P vs NP open).

Why does operator Associativity matter in grammar design, and how is left-associativity encoded?

Associativity fixes grouping for operators of equal precedence (e.g., a−b−c = (a−b)−c). Left-associativity is encoded with left-recursive rules like E→E−T | T; right-associativity uses right recursion like E→T=E | T.

How is operator Precedence expressed in an expression grammar?

By using a separate non-terminal level for each precedence tier, with lower-precedence operators higher in the grammar. E.g., E→E+T|T (addition), T→T*F|F (multiplication, binds tighter), F→(E)|id.

List the standard Grammar Transformations needed for top-down parsing.

Elimination of left recursion (A→Aα|β becomes A→βA', A'→αA'|ε) and left factoring (A→αβ1|αβ2 becomes A→αA', A'→β1|β2). These remove left recursion and common prefixes that block predictive parsing.

What characterizes Top-Down Parsing?

It builds the parse tree from the root (start symbol) down to the leaves, performing a leftmost derivation. It includes recursive-descent and predictive LL parsers; it cannot directly handle left-recursive grammars.

What is Recursive Descent Predictive Parsing?

A top-down method with one (possibly recursive) procedure per non-terminal that consumes input to match productions. The predictive (non-backtracking) form uses lookahead to choose the correct production deterministically.

What conditions make a grammar LL(1)?

For every non-terminal with productions A→α|β: FIRST(α)∩FIRST(β)=∅, and if β⇒*ε then FIRST(α)∩FOLLOW(A)=∅. Equivalently the LL(1) parsing table has no multiply-defined entries. LL(1) grammars are unambiguous and non-left-recursive.

How are FIRST and FOLLOW sets used in LL(1) parsing?

FIRST(α) = set of terminals beginning strings derivable from α (plus ε if α⇒*ε). FOLLOW(A) = terminals that can appear immediately after A. The table entry M[A,a] holds A→α when a∈FIRST(α), and when ε∈FIRST(α), for each b∈FOLLOW(A).

What characterizes Bottom-Up Parsing?

It constructs the parse tree from leaves up to the root by reducing handles, producing a rightmost derivation in reverse. Shift-reduce parsers (LR family) are bottom-up and handle a larger class of grammars than top-down parsers.

Compare the LR parser variants SLR(1), LR(1)/CLR, and LALR(1) by power and table size.

Power: LR(1) > LALR(1) > SLR(1) > LL(1). LR(1)/CLR has the most states (largest tables); LALR(1) merges LR(1) states with identical cores giving the same number of states as SLR but more power (can introduce reduce-reduce conflicts); SLR uses FOLLOW sets and is simplest but weakest of the LR family.

What are the four actions of an LR shift-reduce parser?

Shift (push the input symbol and a state), Reduce (pop the handle and apply a production), Accept (successful parse), and Error. Decisions use the parsing tables ACTION (terminals) and GOTO (non-terminals).

What is an Attribute Grammar?

A context-free grammar augmented with attributes attached to grammar symbols and semantic rules (associated with productions) that compute attribute values. It formalizes the static semantics and syntax-directed translation of a language.

Distinguish Synthesized from Inherited attributes.

A synthesized attribute of a node is computed from attributes of its children (information flows up the parse tree). An inherited attribute is computed from attributes of its parent and/or siblings (information flows down/sideways).

Define S-attributed and L-attributed Syntax-Directed Definitions.

S-attributed: uses only synthesized attributes; evaluable bottom-up in a single pass (suits LR parsing). L-attributed: each inherited attribute of a symbol depends only on attributes of its parent and the siblings to its left (plus any synthesized); evaluable in one left-to-right depth-first pass.

What is a Dependency Graph and how does it determine Evaluation Order?

A directed graph whose nodes are attribute instances and whose edges go from each attribute to those that depend on it. A valid evaluation order is any topological sort of this graph; a cycle means no valid evaluation order exists.

What does Type Checking accomplish in semantic analysis?

It verifies that operations are applied to operands of compatible types using the language's type rules, performs type inference and coercion/conversion where allowed, and reports type errors. It is typically implemented with synthesized type attributes via syntax-directed definitions.

What is an Activation Record (stack frame) and what does it typically contain?

A block of memory for one procedure activation containing: return value, actual parameters, control link (to caller's frame), access/static link, saved machine status (return address, registers), and local/temporary variables.

What is an Activation Tree and how does stack allocation relate to it?

An activation tree depicts the nesting of procedure calls during execution (root = main, children = called procedures). Because calls follow last-in-first-out nesting, activation records are pushed/popped on a run-time stack, mirroring a depth-first traversal of the tree.

Compare call-by-value, call-by-reference, and call-by-name parameter passing.

Call-by-value: the actual's value is copied; callee changes don't affect the caller. Call-by-reference: the actual's address is passed; callee changes affect the caller's variable. Call-by-name: the actual is re-evaluated (textually substituted) on each use. Call-by-value-result copies in and copies the result back on return.

What information does a compiler Symbol Table store and why?

For each identifier it stores name, type, scope, storage/offset, kind (variable, function, parameter), and other attributes. It supports semantic analysis (type checking, scope resolution) and code generation; it is typically implemented as a hash table with scope handling.

Name common Intermediate Representations used in compilers.

Three-address code (e.g., quadruples, triples, indirect triples), syntax trees / DAGs, postfix notation, and static single-assignment (SSA) form. IRs decouple the front end from the back end and ease optimization.

How is a Boolean expression translated using short-circuit (jumping) code?

Boolean operators are translated into conditional jumps rather than computing 0/1 values: for a&&b, if a is false jump to the false-exit; for a||b, if a is true jump to the true-exit. Backpatching fills in jump targets (truelist/falselist) once labels are known. This realizes short-circuit evaluation.

How is an if-then-else / control-flow statement translated to three-address code?

The boolean condition is given true and false target labels; code emits a conditional jump to the false label, the then-block, a jump past the else, the false label, then the else-block, then the merge label. Loops (while) similarly use a begin label, condition test, body, and a jump back.

What is the distinction between Local Optimization and Global Optimization?

Local optimization works within a single basic block (e.g., common-subexpression elimination, constant folding using a DAG). Global optimization spans basic blocks across the whole procedure using control-flow and data-flow analysis (e.g., global CSE, code motion).

What is Data-Flow Analysis and name two classic problems with their direction.

It gathers information about how data values propagate through a program's control-flow graph by solving equations to a fixed point. Reaching definitions and available expressions are forward problems; live variable analysis and very-busy expressions are backward problems.

What is Control-Flow Analysis and what is a basic block?

Control-flow analysis builds the control-flow graph (CFG) and identifies loops and dominators. A basic block is a maximal sequence of consecutive instructions with one entry (a leader) and one exit—no branches in except at the start and none out except at the end.

Describe Loop Optimization techniques.

Loop-invariant code motion (hoist computations that don't change out of the loop), induction-variable elimination/strength reduction (replace expensive ops like multiply with add), and loop unrolling. These reduce work performed per iteration; they target the most frequently executed code.

What is Peephole Optimization?

A machine-dependent technique that examines a small sliding window (peephole) of target/intermediate instructions and replaces inefficient sequences with shorter/faster ones: removing redundant loads/stores, eliminating unreachable code, algebraic simplification, strength reduction, and using machine idioms.

What is Instruction Scheduling and why is it performed?

Reordering instructions to improve performance on pipelined/superscalar processors—filling delay slots, avoiding pipeline stalls, and hiding memory/functional-unit latencies—while preserving data dependences. List scheduling over a dependence DAG is a common approach.

What is a Non-Computational (undecidable) problem, with an example?

A problem for which no algorithm (Turing machine) can produce the correct yes/no answer for all inputs. Examples: the Halting Problem, the Post Correspondence Problem, and determining whether two CFGs are equivalent.

How is the Halting Problem's undecidability typically proven?

By diagonalization/contradiction: assume a decider H(M,w) exists; build D(M) that halts iff H says M loops on M; then D(D) halts iff it loops—a contradiction. Hence no such H exists and halting is undecidable.

How are complexity classes P and NP defined?

P is the class of decision problems solvable by a deterministic TM in polynomial time. NP is the class solvable by a non-deterministic TM in polynomial time, equivalently problems whose 'yes' certificates are verifiable in polynomial time. P⊆NP; whether P=NP is open.

What does NP-complete mean and how is NP-completeness proved?

A problem is NP-complete if it is in NP and every NP problem reduces to it in polynomial time (NP-hard). It is proved by polynomial-time reduction from a known NP-complete problem (e.g., SAT via Cook-Levin theorem). If any NP-complete problem is in P, then P=NP.

How do you construct a Turing machine for a simple problem like recognizing {a^n b^n c^n | n≥1}?

Repeatedly scan the tape: mark the leftmost unmarked a (e.g., as X), move right to mark the next b (Y), then the next c (Z), and return left; loop until all are marked. Accept if every a,b,c is matched in correct order with equal counts; reject otherwise. (This language is context-sensitive, not context-free.)

How is the translation of a declaration like 'int x' handled in syntax-directed translation?

A semantic rule computes the type and width from the type specifier and uses inherited attributes to record each identifier's type, width, and relative storage offset in the symbol table, advancing the offset for the next declaration.

How is an assignment statement translated into three-address code?

Each sub-expression is evaluated into a temporary; the synthesized attribute holds the place (name/temp) of the result. For x = a+b*c, emit t1 = b*c; t2 = a+t1; x = t2. Array and indexed assignments compute the address offset first.

How are Procedure Calls handled at the code-generation/runtime level?

The caller evaluates and passes actual parameters (via the param instruction / pushing onto the stack), saves machine state, sets up the activation record, and transfers control (call). On return the callee restores state, passes back any return value, and control resumes after the call site.