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.
Topic-wise mock tests
- Which of the following Grammars is/are only Context Free?
- Consider the following DFA Which of the following NFA is valid for the given DFA ?
- Consider the following DFA that generates set of Σ = {a, b, c} strings over Now identify that which of the followings is the best description of the language for the above DFA
- Match List I with List II. List I: A. Type 3 Grammar, B. Type 2 Grammar, C. Type 1 Grammar, D. Type 0 Grammar. List II: I. V → (V ∪ Σ)*; II. λVβ → λ(V ∪ Σ)*β, where λ, β ∈ (V ∪ Σ)*; III. (V ∪ Σ)* → (V ∪ Σ)*; IV. V → VΣ…
- Arrange the following parsers in increasing order of their power of handling grammars i.e. from the least powerful parser to the most powerful parser. A. LR (0) B. LR (1) C. LALR(1) D. LL (0) E. SLR
- Which of the following is the Optimized version for the given TAC in the passage
- What all blocks does Block 3 and Block 5 dominate in the Flow graph for the TAC given in the passage?
- Which of the followings is the correct Flow graph for the TAC given in the passage?
- Match the LIST-I with LIST-II
- Match List I with List II. List I: A. Type-0 grammar, B. Type-1 grammar, C. Type-2 grammar, D. Type-3 grammar. List II: I. Linear grammar; II. GNF; III. x → y, |x| ≤ |y|, x, y ∈ (V ∪ T)*; IV. Recursively enumerable.
- For the above mentioned passage which of the following is correct?
- Which of the following represented the minimum state DFA for the above specified passage?
- For the above specified passage, which of the following is DFA for the language represented/accepeted by machine?
- For the above specified passage, which of the following represents the regular expression?
- 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 tasks could be attained using syntax trees in compiler design ? (A) Type Checking (B) Code Generation (C) Code Optimization (D) Error Handling
- Arrange the following stages of parsing in the correct order as they typically occur in the compilation process. (A) Lexical Analysis (B) Sematic Analysis (C) Syntax Analysis (D) Intermediate Code Generation (E) Code Op…
- Arrange the following Language Classes in ascending order according to their expressive power, as defined by Chomsky hierarchy: (A) Context-free languages (B) Context-sensitive languages (C) Regular languages (D) Unrest…
- Which of the following is a context-free language? (A) {wⁱ xʲ yᵏ zˡ | i + k = j + l, i, j, k, l ≥ 0} (B) {wⁱ xʲ yᵏ zˡ | i = j, k = l} (C) {wⁱ xʲ yᵏ zˡ | i = j = k and k ≠ l} (D) {wⁱ xʲ yᵏ zˡ | i = j = k + l} (E) {wⁱ xʲ…
- Match List I with List II. List I: A. A → aB | a (a ∈ T; A, B ∈ V), B. A → BC | a (a ∈ T; A, B, C ∈ V), C. LL(1) grammar, D. Halting problem. List II: I. Recursive descent parser, II. Turing machine, III. Chomsky Normal…
- For the regular languages and context-free languages which is not correct? A. both are closed under union operation B. both are closed under concatenation operation C. both are closed under intersection operation D. bot…
- Match List-I with List-II :
- For the given two machines which of the following is correct?
- Let L= {ab, aa, baa}. Which of the following strings are not in L*?
- Let A={a, b} and L=A*. Let X={anbn, n>0}. The languages L U X and X are respectively :
- Which of the following symbol table implementations is best suited if access time is to be minimum?
- The sum of minimum and maximum number of final states for a Deterministic Finite Automata (DFA) having ' P ' state is equal to :
- Three address codes can be represented in special structures known as : (A) Quadruples (B) Triples (C) Patterns (D) Indirect Triples
- Which of the statement 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 input to the compiler phase that process it :