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.
- For the above specified passage, which of the following represents the grammar for the language accepted by the machine?
- Which of the following represents the minimum-state DFA for the above specified passage?
- For the above specified passage, which of the following is a DFA for the language accepted by the machine?
- For the above specified passage, which of the following represents the regular expression?
- 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₀, $)?
- 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?
- 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 a…
- If L₁ and L₂ are context-free languages, which one of the following is true about L₁ ∩ L₂?
- 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:
- 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 th…
- 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₂…
- 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…
- 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…
- 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…
- Let L = {ab, aa, baa}. Which of the following strings is NOT in L*?
- Let A = {a, b} and L = A*. Let X = {aⁿbⁿ | n > 0}. The languages L ∪ X and X are respectively:
- Which of the following symbol-table implementations is best suited if access time is to be minimum?
- Consider the grammar E → E + n | E × n | n. For the sentence n + n × n, the handles in the right-sentential forms of the reduction are:
- One of the purposes of using intermediate code in compilers is to:
- The sum of the minimum and maximum number of final states for a DFA having P states is equal to:
- Three-address code can be represented in special structures known as: (A) Quadruples (B) Triples (C) Patterns (D) Indirect Triples Choose the correct answer from the options given below:
- Which of the statements is/are CORRECT? (A) Moore and Mealy machines are finite state machines with output capabilities. (B) Any given Moore machine has an equivalent Mealy machine. (C) Any given Mealy machine has an eq…
- Match List I with List II according to the input to the compiler phase that processes it:List I List II (a) Syntax tree (I) Code generator (b) Intermediate representation (II) Semantic analyzer (c) Token stream (III) Le…
- Arrange the following phases of a compiler in their order of execution (start to end): (a) Target code generation (b) Syntax analysis (c) Code optimization (d) Semantic analysis (e) Lexical analysis Choose the correct a…
- 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…
- The maximum yield length of the following CNF CFG is S → AB A → CD B → e C → a D → b
- Consider the language L = {w ∈ {a, b, c}* : nₐ(w) + n_b(w) = n_c(w)}. L is
- 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 T…
- Which phase of the compiler checks the grammar of the program?
- 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 st…