UGC NET · PAPER 2
UGC NET Paper 2 Computer Science – Unit 8: Theory of Computation and Compilers PYQ (June 2024 (Cancelled Exam))
Q2. Shift-reduce conflicts are resolved by:
- Left recursion
- Left factoring
- Ambiguity
- Associativity and precedence
Q5. Match List I with List II
| List I | List II |
|---|---|
| A. A → aB | a (a ∈ T; A, B ∈ V) | I. Recursive Descent Parser |
| B. A → BC | a (a ∈ T; A, B, C ∈ V) | II. Turing Machine |
| C. LL(1) grammar | III. Chomsky Normal Form |
| D. Halting problem | IV. Finite Automata |
- A-IV, B-III, C-I, D-II
- A-III, B-I, C-II, D-IV
- A-II, B-IV, C-III, D-I
- A-IV, B-III, C-II, D-I
Q18. Which of the following is a function of the semantic analysis phase of compilation?
- Type conversion
- Tokenization
- Loop optimization
- Data flow analysis
Q19. For regular languages and context-free languages, which is NOT correct?
A. Both are closed under union
B. Both are closed under concatenation
C. Both are closed under intersection
D. Both are closed under complementation
E. Both are closed under Kleene star
Choose the most appropriate answer from the options given below:
A. Both are closed under union
B. Both are closed under concatenation
C. Both are closed under intersection
D. Both are closed under complementation
E. Both are closed under Kleene star
Choose the most appropriate answer from the options given below:
- A and B Only
- B and C Only
- C and D Only
- D and E Only
Q20. Match List I with List II
| List I | List II |
|---|---|
| A. Back Tracking | I. Automata |
| B. Infinite languages with matching numbers | II. Undecidable Problem |
| C. Canonical LR Parser | III. Predictive Parser |
| D. Post Correspondence Problem | IV. Large number of states |
- A-I, B-II, C-III, D-IV
- A-II, B-III, C-I, D-III
- A-IV, B-III, C-II, D-I
- A-III, B-I, C-IV, D-II
Q32. An ambiguous grammar is one which has:
A. More than one derivation
B. More than one leftmost derivation
C. More than one rightmost derivation
D. More than one parse tree
E. More than one syntax tree
Choose the correct answer from the options given below:
A. More than one derivation
B. More than one leftmost derivation
C. More than one rightmost derivation
D. More than one parse tree
E. More than one syntax tree
Choose the correct answer from the options given below:
- A and D Only
- B and C Only
- D and E Only
- A and E Only
Q50. Arrange in appropriate order the construction of a finite automaton:
A. Minimum-state DFA
B. Regular expression
C. NFA-ε
D. Problem statement
E. DFA
Choose the correct answer from the options given below:
A. Minimum-state DFA
B. Regular expression
C. NFA-ε
D. Problem statement
E. DFA
Choose the correct answer from the options given below:
- B, C, E, A, D
- D, B, C, E, A
- C, E, B, A, D
- A, D, C, B, E
Q52. The grammar
stmt → if expr then stmt else stmt | if expr then stmt
suffers from:
stmt → if expr then stmt else stmt | if expr then stmt
suffers from:
- Ambiguity
- Left factoring
- Left recursion
- λ-moves
Q69. The language of the following PDA would be:
δ(q0, a, z0) = (q0, aaaz0)
δ(q0, a, a) = (q0, aaaa)
δ(q0, b, a) = (q1, λ)
δ(q1, b, a) = (q1, λ)
δ(q1, ε, z0) = (qf, z0), where qf is the final state.
δ(q0, a, z0) = (q0, aaaz0)
δ(q0, a, a) = (q0, aaaa)
δ(q0, b, a) = (q1, λ)
δ(q1, b, a) = (q1, λ)
δ(q1, ε, z0) = (qf, z0), where qf is the final state.
- {aⁿbⁿ | n > 0}
- {aⁿb²ⁿ | n > 0}
- {aⁿb³ⁿ | n > 0}
- {aⁿb⁴ⁿ | n > 0}
Q73. For the given two machines over {a, b}, which of the following is correct?
Machine 1: states A (start), B (final); A –a→ A, A –a→ B, B –b→ B, B –b→ A.
Machine 2: states A (start), B (final), C (final); A –a→ B, B –a→ B, B –b→ C, C –b→ C, C –a→ B.
Machine 1: states A (start), B (final); A –a→ A, A –a→ B, B –b→ B, B –b→ A.
Machine 2: states A (start), B (final), C (final); A –a→ B, B –a→ B, B –b→ C, C –b→ C, C –a→ B.
- Both machines are DFAs
- Both are non-equivalent machines
- Both are equivalent machines
- Cannot be determined
Q74. The number of tokens in the line ' for i in range (begin; end ; step) : ' is:
- 4
- 7
- 8
- 12