Theory of Computation and Compilers – Previous Year Questions
250 questions from past UGC NET Paper 2 – Computer Science papers, each with the correct answer. Open any question for its explanation.
- Which of the following parsers is the most powerful?
- Which of the following statements is correct?
- A compiler for a high-level language that runs on one machine and produces code for another machine is called a
- Shift-reduce conflicts are resolved by:
- Match List I with List IIList 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.…
- Which of the following is a function of the semantic analysis phase of compilation?
- 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 complementatio…
- Match List I with List IIList 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. L…
- 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 a…
- 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:
- The grammar stmt → if expr then stmt else stmt | if expr then stmt suffers from:
- 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.
- 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,…
- The number of tokens in the line ' for i in range (begin; end ; step) : ' is:
- In the pumping lemma for context-free languages, for a string uvwxy, what is the minimum length of vx together?
- Which of the following is an ε-free grammar?
- While processing a string, an LR parser reads the input
- 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 φ?
- 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) = {…
- 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…
- 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 c…
- The precedence of regular-expression operators from lowest to highest is:
- 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?
- The transition function δ in a multi-tape Turing machine (k tapes) is defined as:
- In the pumping lemma for regular languages, writing the string as xyz, what is the minimum length of y?
- The item generated by the production A → ε is:
- 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 {…
- 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…
- 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 in…
- 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: