UGC NET · PAPER 2
UGC NET Paper 2 Computer Science – Unit 8: Theory of Computation and Compilers PYQ (22 June 2026)
Q67. Which of the following is not a part of the general activation record of a procedure?
- Local data
- Global data
- Access link
- Temporaries
Q68. Match the LIST-I with LIST-II.
Choose the correct answer from the options given below:
| LIST-I (Language) | LIST-II (Type of Language) |
|---|---|
| A. L₁ = {aⁿbᵐ | n, m ≥ 0} | I. Unrestricted |
| B. L₂ = {aⁿbᵐ | (n − m) ≥ 0} | II. Context Sensitive |
| C. L₃ = {aⁿbⁿcⁿdⁿ | n ≥ 1} | III. Regular |
| D. L₄ = {aⁿbᵐcᵐdⁿ | n, m ≥ 0} | IV. Context Free |
- A-III, B-I, C-II, D-IV
- A-III, B-IV, C-I, D-II
- A-III, B-II, C-IV, D-I
- A-II, B-III, C-IV, D-I
Q88. If L1 is a regular language and L2 is a context free language, which of the following statement is correct?
- Any subset of L1∪L2 is context free.
- L1∩L2 is a context free language.
- L1∩L2 is a regular language.
- L1∩L2 is accepted by a deterministic push down automaton.
Q92. Given the functions:
Predecessor function: Pred(x) = x − 1
and T(x, y+1) = Pred(T(x, y)), T(x, 0) = x.
Which of the following operations is a candidate for T?
Predecessor function: Pred(x) = x − 1
and T(x, y+1) = Pred(T(x, y)), T(x, 0) = x.
Which of the following operations is a candidate for T?
- Subtraction Operation
- Addition Operation
- Multiplication Operation
- Division Operation
Q99. Arrange the following families of languages from specialization to generalization, defined over alphabet Σ:
A. Family of all regular languages
B. Family of all Turing acceptable languages
C. Family of all Turing decidable languages
D. Family of all context free languages
Choose the correct answer from the options given below:
A. Family of all regular languages
B. Family of all Turing acceptable languages
C. Family of all Turing decidable languages
D. Family of all context free languages
Choose the correct answer from the options given below:
- A, B, C, D
- A, C, B, D
- A, D, C, B
- A, D, B, C
Q119. Which of the following statements is incorrect?
- Given a context free grammar G and a string x, an algorithm can be designed to decide whether x∈L(G) in polynomial time.
- Given a context free language L, its complement is also context free.
- The language {aⁿ bᵐ cᵖ : m, n, p ≥ 0, m≠n or m≠p} is not deterministic context free.
- Class of deterministic context free languages is closed under intersection.
Q124. The minimum state DFA of the following would be the following: (a DFA with states q0 (start), q1, q2, q3 and q4 (accepting) is given, with transitions q0→0 q1, q0→1 q3, q1→0 q1 (self-loop), q1→1 q4, q3→0 q2, q3→1 q4, q2→1 q4, over the alphabet {0,1})
- A –(0,1)→ B, B has a self-loop on 0, B –1→ C
- A –(0,1)→ B, B has a self-loop on 1, B –0→ C
- A –(0,1)→ B, B has a self-loop on (0,1), B –1→ C
- A –(0,1)→ B, B –1→ C (no self-loop shown)
Consider the following Context Free Grammar (G):
S → A B
B → + A B | ε
A → C D
D → * C D | ε
C → [ S ] | x
Variable = { S, A, B, C, D }
Terminals = { +, *, [, ], x }
Q146. Find the Follow (A) & Follow (C).
- Follow (A) = { ], $ }; Follow (C) = { +, ], $ }
- Follow (A) = { +, ], $ }; Follow (C) = { *, +, ], $ }
- Follow (A) = { *, $, [ }; Follow (C) = { *, [, $ }
- Follow (A) = { *, ], $ }; Follow (C) = { +, ], $ }
Q147. In the LL(1) Parsing table of the given CFG, how many valid non-blank entries will be there in the rows for variables 'B' and 'D'?
- B = 3 entries; D = 4 entries
- B = 6 entries; D = 5 entries
- B = 2 entries; D = 3 entries
- B = 1 entry; D = 2 entries
Q148. Identify the correct statement from the following.
- The given CFG(G) is Left recursive
- The given CFG(G) needs Left factorization
- [[x * x] + x] is a valid sentence of this grammar
- The given CFG(G) has an SLR(o) Parser as well
Q149. What will be the FIRST(S) & FIRST(D)?
- FIRST (S) = { +, [, x }; FIRST (D) = { +, * }
- FIRST (S) = { [, ], x }; FIRST (D) = { +, ε }
- FIRST (S) = { [, x }; FIRST (D) = { *, ε }
- FIRST (S) = { [, x, ε }; FIRST (D) = { *, ε }
Q150. The I0 state of the canonical LR(0) set of the SLR(1) parser of this CFG has how many productions?
- 3
- 4
- 5
- 6