UGC NET · PAPER 2
UGC NET Paper 2 Computer Science – Unit 8: Theory of Computation and Compilers PYQ (June 2023)
Q25. Consider a finite automaton F1 with three states C (start), S and E (final), in which there are transitions in both directions between every pair of states (C ⇄ S, S ⇄ E, C ⇄ E). Let F2 be the finite automaton obtained by reversal of F1. Which of the following is correct?
- L(F1) ≠ L(F2)
- L(F1) = L(F2)
- L(F1) ≤ L(F2)
- L(F1) ≥ L(F2)
Q34. The maximum yield length of the following CNF CFG is
S → AB
A → CD
B → e
C → a
D → b
S → AB
A → CD
B → e
C → a
D → b
- 8
- 7
- 4
- 5
Q40. Consider the language L = {w ∈ {a, b, c}* : nₐ(w) + n_b(w) = n_c(w)}. L is
- Context free but not linear
- Not context free
- Context free and linear
- Linear
Q48. Consider the following statements:
A. A context-free language is generated by an LR(0) grammar if and only if it is accepted by a deterministic pushdown automaton and has the prefix property.
B. If M1 is a single-tape TM simulating a multitape TM M, then the time taken by M1 to simulate n moves is O(n³).
C. A pushdown automaton behaves like a Turing machine when it has one auxiliary memory.
D. L = {aⁿbⁿcⁿ : n ≥ 1} is not context-free but is context-sensitive.
Choose the correct answer from the options given below:
A. A context-free language is generated by an LR(0) grammar if and only if it is accepted by a deterministic pushdown automaton and has the prefix property.
B. If M1 is a single-tape TM simulating a multitape TM M, then the time taken by M1 to simulate n moves is O(n³).
C. A pushdown automaton behaves like a Turing machine when it has one auxiliary memory.
D. L = {aⁿbⁿcⁿ : n ≥ 1} is not context-free but is context-sensitive.
Choose the correct answer from the options given below:
- A, B and C only
- A, B only
- D only
- B, C only
Q60. Which phase of the compiler checks the grammar of the program?
- Code optimization
- Semantic analysis
- Code generation
- Syntax analysis
Q66. Consider the following statements:
A. The set of Turing machine codes for TMs that accept all inputs that are palindromes (possibly along with other inputs) is decidable.
B. The language of codes for TMs M that, when started with blank tape, eventually write a 1 somewhere on the tape is undecidable.
C. The language accepted by a TM M, L(M), is always recursive.
D. Post's correspondence problem is undecidable.
Choose the correct answer from the options given below:
A. The set of Turing machine codes for TMs that accept all inputs that are palindromes (possibly along with other inputs) is decidable.
B. The language of codes for TMs M that, when started with blank tape, eventually write a 1 somewhere on the tape is undecidable.
C. The language accepted by a TM M, L(M), is always recursive.
D. Post's correspondence problem is undecidable.
Choose the correct answer from the options given below:
- A, B and C only
- B, C and D only
- A and C only
- B and D only
Q68. Which of the following parsers is the most powerful?
- Operator precedence
- SLR
- Canonical LR
- LALR
Q73. Which of the following statements is correct?
- Ackermann's function is primitive recursive.
- L = {aⁿbᵏcⁿ⁺ᵏ : n ≥ 0, k ≥ 0} is a regular language.
- L = {aⁿbʲ : n = j²} is not a context-free language.
- For every context-sensitive language L not including λ, there exists some linear bounded automaton M such that L ≠ L(M).
Q90. A compiler for a high-level language that runs on one machine and produces code for another machine is called a
- Cross compiler
- Multipass compiler
- Optimizing compiler
- More than one of the above