UGC NET · PAPER 2
UGC NET Paper 2 Computer Science – Unit 8: Theory of Computation and Compilers PYQ (June 2025)
Q14. 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 A → Aa A → ε |
- A, B Only
- C, D Only
- C, E Only
- A, B, D, E Only
Q50. 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):
Which of the following NFAs is valid (equivalent) for the given DFA?
| State | a | b | c |
|---|---|---|---|
| → q0 | q1 | – | – |
| q1 | q2 | q3 | q4 |
| * q2 | q2 | q3 | q4 |
| * q3 | q5 | – | q3 |
| * q4 | q0 | – | – |
| * q5 | q1 | – | – |
- NFA-A: states q0–q4, start q0, final {q2, q3}. q0 –a→ q0, q0 –a→ q1; q1 –b→ q2, q1 –a,c→ q3; q2 –c→ q2, q2 –a→ q0, q2 –a→ q3, q2 –a→ q4; q4 –c→ q3; q3 –a→ q0
- NFA-B: same as NFA-A but final states {q2, q3, q4}
- NFA-C: states q0–q3, start q0, final {q3} only. q0 –a→ q0, q0 –a→ q1; q1 –b→ q2, q1 –a,c→ q3; q2 –c→ q2, q2 –a→ q0, q2 –a→ q3; q3 –a→ q0
- NFA-D: states q0–q3, start q0, final {q2, q3}. q0 –a→ q0, q0 –a→ q1; q1 –b→ q2, q1 –a,c→ q3; q2 –c→ q2, q2 –a→ q0, q2 –a→ q3; q3 –a→ q0
Q75. Consider the following DFA over Σ = {a, b, c}. Start state q0, which is also the only final state. Transitions:
Which of the following is the best description of the language of this DFA?
| 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 |
- L = (a* + b* + c*)⁺
- L = (a + b + c)* (abc)⁺ (a + b + c)*
- L = {set of strings all starting with 'a, b, c' but ending with 'c'}
- L = {set of strings having an even count (including 0) of substring 'abc'}
Q76. Match List I with List II
| List 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Σ | Σ |
- A → II, B → III, C → IV, D → I
- A → III, B → I, C → IV, D → II
- A → IV, B → I, C → II, D → III
- A → III, B → II, C → I, D → IV
Q88. 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 answer from the options given below:
A. LR(0)
B. LR(1)
C. LALR(1)
D. LL(0)
E. SLR
Choose the correct answer from the options given below:
- LL(0) → LR(0) → SLR → LR(1) → LALR(1)
- SLR → LR(0) → LL(0) → LR(1) → LALR(1)
- LL(0) → LR(0) → SLR → LALR(1) → LR(1)
- LR(0) → LL(0) → SLR → LR(1) → LALR(1)
Directions (Q91–95): Consider the following Three Address Code sample for solving the questions:
100: t1 = y + 2 101: initial = x / t1 102: limit = 10 103: if i > j goto 105 104: goto 111 105: if num > b goto 107 106: goto 111 107: num = limit - 1 108: b = y + 2 109: i = i - num 110: goto 103 111: j = i - num 112: k = j + b
Q91. What are the various LEADERS (leading statements) for the TAC given in the passage?
- 100, 102, 103, 104, 105, 107, 110
- 100, 103, 105, 107, 111, 112
- 100, 103, 105, 106, 107, 111
- 100, 103, 104, 105, 106, 107, 111
Q92. Which of the following is the optimized version of the TAC given in the passage?
100: t1 = y + 2 101: initial = x / t1 102: limit = 10 103: if i > j goto 105 104: goto 111 105: if num > b goto 110 106: goto 111 107: b = y + 2 108: i = i - limit - 1 109: goto 103 110: k = i + b
100: t1 = y + 2 101: initial = x / t1 102: limit = 10 103: if i > j goto 105 104: if num < b goto 111 105: num = limit - 1 106: b = t1 107: i = i - num 108: goto 103 109: k = i + b
100: t1 = y + 2 101: limit = 10 102: num = 9 103: b = t1 104: if i > j goto 106 105: goto 110 106: if num > b goto 108 107: goto 110 108: i = i - num 109: goto 104 110: j = i - num 111: k = j + b
100: t1 = y + 2 101: initial = x / t1 102: limit = 10 103: if i > j goto 105 104: goto 111 105: if num < b goto 111 106: num = limit - 1 107: b = t1 108: i = i - num 109: goto 103 110: k = i + b
Q93. Which of the following is the correct high level code for the TAC given in the passage?
t1 = y+2; init = x/t1; limit = 10; if (i>j || num>b) { num = limit-1; b = y+2; i = i-num; } j = i-num; k = k+b;init = x/(y+2); limit = 10; while (i>j || num>b) { num = limit-1; b = y+2; i = i-num; } j = i-num; k = k+b;init = x/(y+2); limit = 10; if (i>j) { while (num>b) num = limit-1; } else { b = y+2; i = i-num; } j = i-num; k = k+b;init = x/(y+2); limit = 10; while (i>j && num>b) { num = limit-1; b = y+2; i = i-num; } j = i-num; k = k+b;
Q94. 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)
- Block 3: 3; Block 5: 5
- Block 3: 3, 4, 5, 6; Block 5: 5, 6
- Block 3: 3, 7; Block 5: 5, 7
- Block 3: 3, 4, 7; Block 5: 5, 6, 7
Q95. 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?
0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0