UGC NET · PAPER 2
UGC NET Paper 2 Computer Science – Unit 8: Theory of Computation and Compilers PYQ (December 2024)
Q19. Which of the following is TRUE about the Pumping Lemma for regular languages?
- It is a property used to prove that languages are not regular
- It applies only to infinite regular languages
- It applies to all context-free languages
- It applies to all recursively enumerable languages
Q31. 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 target code
Choose the correct answer from the options given below:
A. Algebraic Simplification
B. Use of machine idioms
C. Redundant-instruction elimination
D. Flow of control optimization
E. Improved target code
Choose the correct answer from the options given below:
- A, C, B, D, E
- B, C, D, A, E
- C, D, A, B, E
- D, B, A, C, E
Q37. 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, L)
δ(q2, a) = (q2, a, L)
δ(q2, x) = (q0, x, R)
δ(q0, y) = (q3, y, R)
δ(q3, y) = (q3, y, R)
δ(q3, □) = (qf, □, R)
δ(q0, a) = (q1, x, R)
δ(q1, a) = (q1, a, R)
δ(q1, y) = (q1, y, R)
δ(q1, b) = (q2, y, L)
δ(q2, y) = (q2, y, L)
δ(q2, a) = (q2, a, L)
δ(q2, x) = (q0, x, R)
δ(q0, y) = (q3, y, R)
δ(q3, y) = (q3, y, R)
δ(q3, □) = (qf, □, R)
- L = {aⁿbⁿ | n ≥ 0}
- L = {aⁿbⁿ | n ≥ 1}
- L = {aⁿbⁿ | n > 0}
- L = {aⁿbⁿ | n > 1}
Q43. Match List I with List II
| List 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 Acyclic Graph (DAG) |
- A-III, B-II, C-IV, D-I
- A-II, B-IV, C-I, D-III
- A-II, B-III, C-I, D-IV
- A-IV, B-I, C-II, D-III
Q56. Match List I with List II
| List 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 |
- A-I, B-II, C-III, D-IV
- A-II, B-I, C-III, D-IV
- A-III, B-II, C-IV, D-I
- A-IV, B-III, C-I, D-II
Q66. 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, Q → r | s
D. M → MN | MP, N → nm | n, P → p
Choose the correct answer from the options given below:
A. S → ABC | AB, A → a, B → b, C → d
B. X → RT | TR, T → t, R → XT | r
C. P → qP | sQ, Q → r | s
D. M → MN | MP, N → nm | n, P → p
Choose the correct answer from the options given below:
- A & B only
- B only
- C only
- B & D only
Q74. yacc is which of the following parsers?
- Predictive Parser
- SLR Parser
- CLR Parser
- LALR Parser
Directions (Q91–95): A machine is represented by states Q, input alphabet Σ, transition function δ, initial state q0 and final states F. The machine accepts all strings over Σ = {a, b} which start and end with any combination of the alphabet symbols, and in which abb occurs as a substring (i.e. the language of all strings over {a, b} containing abb).
Q91. For the above-mentioned passage, which of the following automata is correct? Each option is described by its transitions (start state 1).
- States 1–4, final {4}: 1 –a,b→ 1, 1 –a→ 2, 2 –b→ 3, 3 –b→ 4
- States 1–4, final {4}: 1 –a→ 2, 2 –b→ 3, 3 –b→ 4, 4 –a,b→ 4
- States 1–4, final {4}: 1 –a,b→ 1, 1 –a→ 2, 2 –b→ 3, 3 –b→ 4, 4 –a,b→ 4
- States 1–3, start and final {1}: 1 –a,b→ 1, 1 –a→ 2, 2 –b→ 3, 3 –b→ 1
Q92. For the above specified passage, which of the following represents the grammar for the language accepted by the machine?
- S → AabbB, A → aA | ε, B → bB | ε
- S → abbA, A → aA | ε | bA
- S → AabbA, A → aA | bA | ε
- S → Aabb, A → aA | bA | ε
Q93. Which of the following represents the minimum-state DFA for the above specified passage?
- States 1–5, final {4, 5}: 1 –a→ 1, 1 –a→ 2, 2 –a→ 2, 2 –a→ 3, 3 –b→ 2, 3 –b→ 4, 4 –a→ 4, 4 –b→ 5, 5 –a→ 4
- States 1–4, final {4}: 1 –b→ 1, 1 –a→ 2, 2 –a→ 2, 2 –a→ 3, 3 –b→ 2, 3 –b→ 4, 4 –a,b→ 4
- States 1–6, final {4, 5, 6}: 1 –a→ 2, 2 –a→ 2, 2 –b→ 3, 3 –a→ 2, 3 –b→ 4, 4 –b→ 4, 4 –a→ 5, 5 –b→ 6, 6 –a→ 6, 6 –a→ 5
- All are NFA
Q94. For the above specified passage, which of the following is a DFA for the language accepted by the machine?
- States 1–4, final {4}: 1 –a,b→ 1, 1 –a→ 2, 2 –b→ 3, 3 –b→ 4, 4 –a,b→ 4
- States 1–4, final {4}: 1 –b→ 1, 1 –a→ 2, 2 –a→ 2, 2 –b→ 3, 3 –b→ 4, 4 –a,b→ 4
- States 1–6, final {4, 5, 6}: 1 –b→ 1, 1 –a→ 2, 2 –a→ 2, 2 –b→ 3, 3 –a→ 2, 3 –b→ 4, 4 –b→ 4, 4 –a→ 5, 5 –a→ 5, 5 –b→ 6, 6 –a→ 5, 6 –b→ 4
- States 1–6, final {4, 5, 6}: 1 –a→ 1, 1 –b→ 2, 2 –a→ 2, 2 –b→ 3, 3 –a→ 2, 3 –b→ 4, 4 –a→ 4, 4 –b→ 5, 5 –b→ 5, 5 –a→ 6, 6 –b→ 5
Q95. For the above specified passage, which of the following represents the regular expression?
- (a + b)* aab
- aba (a + b)*
- b (a + b)* b (a + b)* a (a + b)*
- (a + b)* abb (a + b)*