Theory of Computation and Compilers – Previous Year Questions
250 questions from past UGC NET Paper 2 – Computer Science papers, each with the correct answer. Open any question for its explanation.
- Which of the following is not a part of the general activation record of a procedure?
- Match the LIST-I with LIST-II. 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…
- If L1 is a regular language and L2 is a context free language, which of the following statement is correct?
- 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?
- 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 decidab…
- Which of the following statements is incorrect?
- 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…
- Find the Follow (A) & Follow (C).
- 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'?
- Identify the correct statement from the following.
- What will be the FIRST(S) & FIRST(D)?
- The I0 state of the canonical LR(0) set of the SLR(1) parser of this CFG has how many productions?
- Which of the following Grammars is/are only Context Free (i.e. context-free but not regular grammars)?Grammar Productions A S → Ab aS → aA A → a B S → Ab A → Sa A → a C S → AS S → aA A → a D S → Ab S → aA A → a E S → Sb…
- Consider the following DFA over Σ = {a, b, c}. Start state q0; final states q2, q3, q4, q5. Transitions (any missing transition goes to a dead state):State a b c → q0 q1 – – q1 q2 q3 q4 * q2 q2 q3 q4 * q3 q5 – q3 * q4 q…
- Consider the following DFA over Σ = {a, b, c}. Start state q0, which is also the only final state. Transitions:State a b c →* q0 q1 q0 q0 q1 q1 q2 q0 q2 q1 q0 q3 q3 q4 q3 q3 q4 q4 q5 q3 q5 q4 q3 q0 Which of the followin…
- Match List I with List IIList I List II A. Type 3 Grammar I. V → (V ∪ Σ)* B. Type 2 Grammar II. αVβ → α(V ∪ Σ)⁺β, where α, β ∈ (V ∪ Σ)* C. Type 1 Grammar III. (V ∪ Σ)* → (V ∪ Σ)* D. Type 0 Grammar IV. V → VΣ | Σ
- Arrange the following parsers in increasing order of their power of handling grammars, i.e. from the least powerful parser to the most powerful parser. A. LR(0) B. LR(1) C. LALR(1) D. LL(0) E. SLR Choose the correct ans…
- What are the various LEADERS (leading statements) for the TAC given in the passage?
- Which of the following is the optimized version of the TAC given in the passage?
- Which of the following is the correct high level code for the TAC given in the passage?
- What blocks do Block 3 and Block 5 dominate in the flow graph for the TAC given in the passage? (Basic blocks: B1 = 100–102, B2 = 103, B3 = 104, B4 = 105, B5 = 106, B6 = 107–110, B7 = 111–112)
- Which of the following is the correct flow graph (adjacency matrix of basic blocks B1–B7, row → column means an edge) for the TAC given in the passage?
- Which of the following is TRUE about the Pumping Lemma for regular languages?
- Regarding code optimization (peephole optimization), choose the correct sequence A. Algebraic Simplification B. Use of machine idioms C. Redundant-instruction elimination D. Flow of control optimization E. Improved targ…
- Which of the following represents the language accepted by the Turing machine with the transition function (δ): δ(q0, a) = (q1, x, R) δ(q1, a) = (q1, a, R) δ(q1, y) = (q1, y, R) δ(q1, b) = (q2, y, L) δ(q2, y) = (q2, y,…
- Match List I with List IIList I List II A. Conflict Resolution I. Three-Address Code B. Common Subexpression II. Precedence C. Quadruples III. Syntax Directed Translations D. L-Attributed definitions IV. Directed Acycli…
- Match List I with List IIList I List II A. Type-0 Grammar I. Linear Grammar B. Type-1 Grammar II. GNF C. Type-2 Grammar III. x → y, |x| ≤ |y|; x, y ∈ (V ∪ T)* D. Type-3 Grammar IV. Recursively Enumerable
- Which of the following CFG(s) is/are in Chomsky Normal Form? (All capital letters are variables & lower case letters are terminals) A. S → ABC | AB, A → a, B → b, C → d B. X → RT | TR, T → t, R → XT | r C. P → qP | sQ,…
- yacc is which of the following parsers?
- For the above-mentioned passage, which of the following automata is correct? Each option is described by its transitions (start state 1).