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.
- Consider L = {ab, aa, baa}. Which string is NOT in L*?
- Consider the NPDA ({q0, q1, qf}, {a, b}, {1, z}, δ, q0, z, {qf}) with δ(q0, λ, z) = {(qf, z)}, δ(q0, a, z) = {(q1, 11z)}, δ(q1, a, 1) = {(q1, 111)}, δ(q1, b, 1) = {(q1, λ)}, δ(q1, λ, z) = {(qf, z)}. Which language does…
- Consider two PCP instances over {0, 1}, each with lists A and B of three strings. X: A = (1, 10111, 10), B = (111, 10, 0). Y: A = (10, 011, 101), B = (101, 11, 011). Which is true?
- Match List I with List II. List I: (A) Activation record, (B) Location counter, (C) Reference count, (D) Address relocation. List II: (I) Linker/loader, (II) Garbage collection, (III) Subroutine call, (IV) Assembler.
- Consider the grammar S → SbS | a. The string abababa has (A) two parse trees (B) two leftmost derivations (C) two rightmost derivations. Which is correct?
- Match List I with List II. List I: (A) Type 0, (B) Type 1, (C) Type 2, (D) Type 3. List II: (I) Finite automata, (II) Turing machine, (III) Linear bounded automata, (IV) Pushdown automata.
- Statement I: The LALR parser is more powerful than the canonical LR parser. Statement II: The SLR parser is more powerful than LALR. Which is correct?
- Statement I: CFLs are closed under homomorphism. Statement II: CFLs are closed under complement. Which is correct?
- Assertion (A): A load-and-go assembler avoids the overhead of writing the object program out and reading it back in. Reason (R): This can be done with either a one-pass or a two-pass assembler.
- Which of the following languages are not regular? A. L = {(01)ⁿ0ᵏ | n > k, k ≥ 0} B. L = {cⁿbᵏaⁿ⁺ᵏ | n ≥ 0, k ≥ 0} C. L = {0ⁿ1ᵏ | n ≠ k}
- Any string of terminals generated by the CFG S → XY, X → 0X | 1X | 0, Y → Y0 | Y1 | 0 (S is the start symbol)
- Let L1 = {0ⁿ1ⁿ0ᵐ | n ≥ 1, m ≥ 1}, L2 = {0ⁿ1ᵐ0ᵐ | n ≥ 1, m ≥ 1}, L3 = {0ⁿ1ⁿ0ⁿ | n ≥ 1}. Which are correct? A. L3 = L1 ∩ L2. B. L1 and L2 are context free but L3 is not. C. L1 and L2 are not context free but L3 is. D. L1…
- Given below are two statements Statement I: The family of context free languages is closed under homomorphism Statement II: The family of context free languages is closed under reversal In light of the above statements,…
- What is the minimum number of states required to the finite automaton equivalent to the transition diagram given below?
- Find the regular expression for the language accepted by the automata given below.
- What language is accepted by the PDA M = ({q0, q1, q2}, {a, b}, {a, b, z}, δ, q0, z, {q2}) where in q0 every input symbol is pushed, δ(q0, λ, a) = {(q1, a)}, δ(q0, λ, b) = {(q1, b)}, in q1 a matches a and b matches b (p…
- Match List I (production rules) with List II (grammar). List I: A. S → XY, X → 0, Y → 1. B. S → aS | bSS | c. C. S → AB, A → 0A | 1A | 0, B → 0A. D. S → aAbc, Ab → bA, Ac → Bbcc, bB → Bb, aB → aa | aaA. List II: I. Grei…
- Which of the following concepts can be used to identify loops? A. Depth first ordering B. Dominators C. Reducible graphs
- Given below are two statements Statement I: LL(1) and LR are examples of Bottom‐up parsers. Statement II: Recursive descent parser and SLR are examples of Top‐down parsers In light of the above statements, choose the co…
- Let L = L₁ ∩ L₂, where L₁ = {0ᵐ1ᵐ2 0ⁿ1ⁿ | m, n ≥ 0} and L₂ = {0ᵐ1ⁿ2ᵏ | m, n, k ≥ 0}. Then L is
- Let 1 and 2 be languages over represented by the regular expressions (a∗ + b)∗ (a + b)∗ and respectively. Which of the following is true with respect to the two languages?
- Which of the following statements is true?
- Which of the following is not an intermediate code form?
- Which of the following are applications of symbol table? (A) Storage allocation (B) Checking type compatability (C) Suppressing duplicate error messages
- Let G1 and G2 be arbitrary context-free grammars and R an arbitrary regular language. Which problems are undecidable? (A) Is L(G1) = L(G2)? (B) Is L(G2) ⊆ L(G1)? (C) Is L(G1) = R?
- Consider L1 = {a^(z²) | z is an integer}, L2 = {a^(2z) | z ≥ 0}, L3 = {ωω | ω ∈ {a, b}*}. Which of the languages is (are) regular?
- Which of the following grammars is (are) ambiguous? (A) S → SS | aSb | bSa | λ (B) S → aSbS | bSaS | λ (C) S → aAB, A → bBb, B → A | λ, where λ denotes the empty string
- Match List I with List II (L_R regular, L_CF context-free, L_REC recursive, L_RE recursively enumerable). List I: A. Recursively enumerable language, B. Recursive language, C. Context-free language. List II: I. compleme…
- Consider the regular expressions r = a(b + a)*, s = a(a + b)⁺, t = aa*b. Which relation holds between the languages they generate?
- Given below are two statements: L ∧ L = ϕ Statement I : The problem "Is 1 2 ? " is L undecidable for context sensitive languages 1 L and 2. ∈ Statement II : The problem "Is W L?" is decidable W for context sensitive lan…