UGC NET · PAPER 2
UGC NET Paper 2 Computer Science – Unit 8: Theory of Computation and Compilers PYQ (December 2022 Shift 1)
Q29. In the pumping lemma for context-free languages, for a string uvwxy, what is the minimum length of vx together?
- 0
- 1
- 2
- n
Q31. While processing a string, an LR parser reads the input
- From right to left
- From left to right
- Either from left to right or right to left
- From the centre of the string
Q32. What are the minimum and maximum numbers of initial, dead, unreachable and final states in a valid n-state finite automaton whose accepted language is not φ?
- Minimum: 1, 1, 1, 1; Maximum: 1, (n−1), (n−1), n
- Minimum: 1, 0, 0, 0; Maximum: 1, (n−1), (n−1), n
- Minimum: 1, 0, 0, n; Maximum: 1, n, (n−1), (n−1)
- Minimum: 1, 0, 0, 1; Maximum: 1, (n−1), (n−1), n
Q59. Which of the following finite automata recognise the language L = {a, b}*?
A. M = ({q0}, {a, b}, δ, q0, {q0}) with δ(q0, a) = {q0}, δ(q0, b) = {q0}
B. M = ({q0, q1}, {a, b}, δ, q0, {q0, q1}) with δ(q0, a) = δ(q0, b) = {q0, q1}, δ(q1, a) = δ(q1, b) = {q1}
C. M = ({q0, q1}, {a, b}, δ, q0, {q0, q1}) with δ(q0, a) = {q0, q1}, δ(q0, b) = {q0}, δ(q1, a) = –, δ(q1, b) = {q1}
D. M = ({q0, q1, q2}, {a, b}, δ, q0, {q0}) with δ(q0, a) = δ(q0, b) = {q0}, δ(q1, a) = {q2}, δ(q1, b) = –, δ(q2, a) = {q0}, δ(q2, b) = {q2}
A. M = ({q0}, {a, b}, δ, q0, {q0}) with δ(q0, a) = {q0}, δ(q0, b) = {q0}
B. M = ({q0, q1}, {a, b}, δ, q0, {q0, q1}) with δ(q0, a) = δ(q0, b) = {q0, q1}, δ(q1, a) = δ(q1, b) = {q1}
C. M = ({q0, q1}, {a, b}, δ, q0, {q0, q1}) with δ(q0, a) = {q0, q1}, δ(q0, b) = {q0}, δ(q1, a) = –, δ(q1, b) = {q1}
D. M = ({q0, q1, q2}, {a, b}, δ, q0, {q0}) with δ(q0, a) = δ(q0, b) = {q0}, δ(q1, a) = {q2}, δ(q1, b) = –, δ(q2, a) = {q0}, δ(q2, b) = {q2}
- A and B
- A and D
- A, B and C
- A, B, C and D
Q60. Which of the following statements are correct?
A. Syntax-directed translation can be applied in type checking.
B. Syntax-directed translation can be used in 3-address code generation.
C. Syntax-directed translation can be used in the construction of syntax trees.
D. Syntax-directed translation can be used to recognise valid tokens.
Choose the most appropriate answer from the options given below:
A. Syntax-directed translation can be applied in type checking.
B. Syntax-directed translation can be used in 3-address code generation.
C. Syntax-directed translation can be used in the construction of syntax trees.
D. Syntax-directed translation can be used to recognise valid tokens.
Choose the most appropriate answer from the options given below:
- A, B and C
- A, B, and D
- A, C and D
- B, C and D
Q73. Match List I with List II (stack and input configurations)
| List I | List II |
|---|---|
| A. Initial configuration of stack and input in LL parsing | I. $ | w$ |
| B. Final configuration of stack and input in LL parsing | II. $ | $ |
| C. Initial configuration of stack and input in LR parsing | III. $S | w$ |
| D. Final configuration of stack and input in LR parsing | IV. $S | $ |
- A-III, B-IV, C-I, D-II
- A-III, B-II, C-I, D-IV
- A-II, B-III, C-IV, D-I
- A-II, B-IV, C-I, D-III
Q83. The precedence of regular-expression operators from lowest to highest is:
- Star, Concatenation, Union
- Union, Star, Concatenation
- Union, Concatenation, Star
- Star, Union, Concatenation
Q89. Consider the following statements:
A. For every regular language, we can design a Turing machine.
B. For every context-free language, we can design a Turing machine.
Which of the following is correct?
A. For every regular language, we can design a Turing machine.
B. For every context-free language, we can design a Turing machine.
Which of the following is correct?
- Statement A is false and Statement B is true.
- Statement A and Statement B are both false.
- Statement A is true and Statement B is false.
- Statement A and Statement B are both true.