UGC NET · PAPER 2
UGC NET Paper 2 Computer Science – Unit 8: Theory of Computation and Compilers PYQ (December 2022 Shift 2)
Q29. The transition function δ in a multi-tape Turing machine (k tapes) is defined as:
- δ : 2Q × Γk → 2Q × Γk × {L, R, S}k
- δ : Q × Q × Γk → Q × Q × Γk × {L, R, S}k
- δ : Q × Γk → Q × Γk × {L, R, S}k
- δ : Q × Γk × 2Q → Q × Γk × 2Q × {L, R, S}k
Q30. In the pumping lemma for regular languages, writing the string as xyz, what is the minimum length of y?
- n
- 2
- 1
- 0
Q32. In the ε-NFA M = ({q0, q1, q2, q3}, {a}, δ, q0, {q3}), where δ is given in the transition table below, what is the minimum length of string to reach the final state?
| State | ε | a |
|---|---|---|
| q0 | {q1} | { } |
| q1 | {q2} | { } |
| q2 | { } | {q2, q3} |
| q3 | { } | { } |
- 0
- 1
- 2
- 3
Q58. Which of the following is (are) correct about the regular expression a a* b b* c c* d d*?
1. The language for the given expression is L = {anbncmdm | n ≥ 1, m ≥ 1} ∪ {anbmcmdn | n ≥ 1, m ≥ 1}
2. The context-free grammar for the given expression is:
S → AB | C
A → aAb | ab
B → cBd | cd
C → aCd | aDd
D → bDc | bc
3. The language generated by this expression is an equal number of a's, followed by an equal number of b's, followed by an equal number of c's, followed by an equal number of d's.
Choose the correct answer from the options given below:
1. The language for the given expression is L = {anbncmdm | n ≥ 1, m ≥ 1} ∪ {anbmcmdn | n ≥ 1, m ≥ 1}
2. The context-free grammar for the given expression is:
S → AB | C
A → aAb | ab
B → cBd | cd
C → aCd | aDd
D → bDc | bc
3. The language generated by this expression is an equal number of a's, followed by an equal number of b's, followed by an equal number of c's, followed by an equal number of d's.
Choose the correct answer from the options given below:
- Only 1 is correct
- Only 2 is correct
- Both 1 and 2 are correct
- All the three 1, 2 and 3 are correct
Q59. Which of the following statements are correct?
1. The first three-address instruction in the intermediate code is a leader.
2. The instruction exactly in the middle of the given three-address code is a leader.
3. Any instruction that is the target of a conditional or unconditional jump is a leader.
4. Any instruction that immediately follows a conditional or unconditional jump is a leader.
Choose the correct answer from the options given below:
1. The first three-address instruction in the intermediate code is a leader.
2. The instruction exactly in the middle of the given three-address code is a leader.
3. Any instruction that is the target of a conditional or unconditional jump is a leader.
4. Any instruction that immediately follows a conditional or unconditional jump is a leader.
Choose the correct answer from the options given below:
- 1, 2 and 3
- 2, 3 and 4
- 1, 3, 4
- 1, 2, 3, 4
Q60. Which of the following are correct for regular expressions?
a. φ + L = L + φ = L
b. εL = Lε = L
c. φL = Lφ = φ
d. φL = Lφ = L
Choose the correct answer from the options given below:
a. φ + L = L + φ = L
b. εL = Lε = L
c. φL = Lφ = φ
d. φL = Lφ = L
Choose the correct answer from the options given below:
- a, b and d only
- a, b and c only
- b and d only
- a and d only
Q73. Match the following based on the lengths of strings in the language accepted (using the brute-force method of parsing).
Choose the correct answer from the options given below:
Choose the correct answer from the options given below:
| List I | List II |
|---|---|
| a. S → aSa | aa | I. ((2n × 3) − 4); n ≥ 1 |
| b. S → aaSaa | aa | II. 2n; n ≥ 1 |
| c. S → aaaSaaa | aa | III. ((4 × 2n) − 6); n ≥ 1 |
| d. S → aaaaSaaaa | aa | IV. 2n − 2; n ≥ 2 |
- a-IV, b-III, c-I, d-II
- a-II, b-IV, c-I, d-III
- a-I, b-IV, c-III, d-II
- a-II, b-III, c-I, d-IV
Q83. What is the safest order for simplifying a context-free grammar?
- Elimination of ε-productions, unit productions, and then useless symbols and productions
- Elimination of useless symbols and productions, ε-productions, and then unit productions
- Elimination of unit productions, ε-productions, and then useless symbols and productions
- Elimination of ε-productions, useless symbols and productions, and then unit productions
Directions (Q96–100): A Turing machine for the language L = {anbmcndm | n ≥ 1, m ≥ 1} is designed. The model is M = ({q0, q1, q2, q3, q4, q5, q6, q7, qf}, {a, b, c, d}, {a, b, c, d, X1, X2, Y1, Y2, B}, δ, q0, B, {qf}), and part of δ is given in the transition table below. X1 and X2 are used to mark a's and c's, and Y1 and Y2 to mark b's and d's.
| a | b | c | d | X1 | X2 | Y1 | Y2 | B | |
|---|---|---|---|---|---|---|---|---|---|
| q0 | (q1, X1, R) | M2 | |||||||
| q1 | (q1, a, R) | (q1, b, R) | M1 | (q1, X2, R) | |||||
| q2 | (q2, a, L) | (q2, b, L) | (q2, X1, R) | (q2, X2, L) | |||||
| q3 | M3 | (q4, Y1, R) | (q6, X2, R) | ||||||
| q4 | (q4, b, R) | (q5, Y2, L) | M5 | (q4, Y2, R) | |||||
| q5 | (q5, b, L) | (q5, X2, L) | M4 | (q5, Y2, L) | |||||
| q6 | (q6, X2, R) | (q7, Y2, R) | |||||||
| q7 | (q7, Y2, R) | (qf, B, R) |
Q96. What is the move in the cell numbered M1 of the table?
- (q2, X2, R)
- (q2, X2, L)
- (q3, X2, L)
- Error entry
Q97. What is the move in the cell numbered M2 of the table?
- (q1, X1, R)
- (q1, a, R)
- (q2, X1, R)
- Error entry
Q98. What is the move in the cell numbered M3 of the table?
- (q1, X1, L)
- (q4, X1, R)
- (q1, X1, R)
- Error entry
Q99. What is the move in the cell numbered M4 of the table?
- (q5, Y1, L)
- (q3, Y1, R)
- (q4, Y1, L)
- Error entry
Q100. What is the move in the cell numbered M5 of the table?
- (q4, X2, R)
- (q5, X2, R)
- (q5, X2, L)
- Error entry