UGC NET Paper 2 Computer Science – Unit 8: Theory of Computation and Compilers PYQ (June 2024 Re-Exam)

Q1. Consider the grammar:
S → A
A → $B$ | id
B → B, A | A
If I₀ = CLOSURE({[S → ·A]}), then how many items will be in the set GOTO(I₀, $)?

Q18. Consider the grammar:
T → Qx
Q → RS
R → y | ε
S → z | ε
Here x, y, z are terminals and T, Q, R, S are non-terminals. What will be the FOLLOW set of the non-terminal R?

Q20. Which of the following properties correctly describe a Regular Grammar?
(A) All production rules are of the form A → xB or A → x, where A and B are non-terminal symbols and x is a terminal symbol.
(B) Regular grammars are more powerful than context-free grammars and can express any type of language.
(C) There is a direct correspondence between regular grammars and finite automata.
(D) Regular grammars can generate languages that are not recognised by any type of automata.
Choose the correct answer from the options given below:

Q49. If L₁ and L₂ are context-free languages, which one of the following is true about L₁ ∩ L₂?

Q51. Which of the following tasks could be attained using syntax trees in compiler design?
(A) Type Checking
(B) Code Generation
(C) Code Optimization
(D) Error Handling
Choose the correct answer from the options given below:

Q63. Arrange the following stages of a Turing Machine (TM) operation in the correct order as they occur during computation.
(A) Writing a symbol on the tape
(B) Moving the tape head left or right
(C) Reading a symbol from the tape
(D) Transitioning to a new state based on the current state and symbol read
(E) Halting and accepting or rejecting the input
Choose the correct answer from the options given below:

Q65. Which of the following languages can be recognized by a Non-Deterministic Finite Automaton (NFA) but cannot be recognized by a Deterministic Finite Automaton (DFA)?
(A) L₁ = {w ∈ {0,1}* | the length of w is even}
(B) L₂ = {w ∈ {0,1}* | the length of w is odd}
(C) L₃ = {w ∈ {0,1}* | all 0's come before all 1's in w}
(D) L₄ = {w ∈ {0,1}* | w contains an equal number of 0's and 1's}
(E) L₅ = {w ∈ {0,1}* | all 1's come before all 0's in w}

Q71. Arrange the following phases in the correct order as they typically occur in the compilation process.
(A) Lexical Analysis
(B) Semantic Analysis
(C) Syntax Analysis
(D) Intermediate Code Generation
(E) Code Optimization
Choose the correct answer from the options given below:

Q77. Arrange the following language classes in ascending order of their expressive power, as defined by the Chomsky hierarchy:
(A) Context-free languages
(B) Context-sensitive languages
(C) Regular languages
(D) Unrestricted grammars (recursively enumerable)
Choose the correct answer from the options given below:

Q90. Which of the following are context-free languages?
(A) {wⁱ xʲ yᵏ zˡ | i + k = j + l, where i, j, k, l ≥ 0}
(B) {wⁱ xʲ yᵏ zˡ | i = j, k = l, where i, j, k, l ≥ 0}
(C) {wⁱ xʲ yᵏ zˡ | i = j = k and k ≠ l, where i, j, k, l ≥ 0}
(D) {wⁱ xʲ yᵏ zˡ | i = j = k + l, where i, j, k, l ≥ 0}
(E) {wⁱ xʲ yᵏ zˡ | i = j = l and k ≠ l, where i, j, k, l ≥ 0}