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.
- Consider the following grammars : G : S → aSb|bSa|aa 1 G : S → aSb|bSa|SS ∣ λ 2 G : S → aSb|bSa|SS ∣ a 3 G : S → aSb|bSa|SS|SSS|λ 4 Which of the following is correct w.r.t. the above grammars? G G
- Which grammar generates L = {aⁿbⁿ⁻³ | n > 2} over Σ = {a, b}?
- Consider the following grammar : S → 0A ∣ 0BB A → 00A ∣ λ B → 1B ∣ 11C C → B Which language does this grammar generate?
- Let Σ = {w, x} and T = {x, y, z}, with homomorphism h(x) = xzy and h(w) = zxyy. If L is denoted by r = (w + x*)(ww)*, then h(L) is denoted by
- Consider the following statements with respect L = {anbn ∣ n ≥ 0} to the language S : L2 1 is context free language S : Lk 2 is conext-free language for any given k ≥ 1 ¯¯¯ S : L L∗ 3 and are context free languages Whic…
- Consider the following languages : L = {anbncm} ∪ {anbmcm}, n, m ≥ 0 1 L = {wwR ∣ w ∈ {a, b}*} 2 Where R represents reversible operation. Which one of the following is (are) inherently ambiguous language(s)? L
- Let G=(V, T, S, P) be any context-free grammar λ without any -productions or unit productions. Let K be the maximum number of symbols on the right of any production in P. The maximum number of production rules for any e…
- Consider the following language families : L ≡ The context - free languages 1 L ≡ The context - sensitive languages 2 L 3 ≡ The recursively enumerable languages L ≡ The recursive languages 4 Which one of the following o…
- Consider the following statements : S 1 : These exists no algorithm for deciding if any M M two Turing machines 1 and 2 accept the same language. S M M 2 : Let 1 and 2 be arbitrary Turing ⊆ L (M ) machines. The problem…
- Let A = {001, 0011, 11, 101} and B = {01, 111, 111, 010}; C = {00, 001, 1000} and D = {0, 11, 011}. Which pairs have a Post correspondence solution?
- Which data structure is used by the compiler for managing variables and their attributes?
- On translating the expression given below into quadruple representation, how many operations are required? (i*j)+(e+f)*(a*b+c)
- Replacing the expression by 8.56 is known as
- Shift-reduce parser consists of (a) input buffer (b) stack (c) parse table
- How many states are there in a minimum state automata equivalent to regular expression given below? a * b(a + b) Regular expression is
- Match List I with List II, where L1 is regular, L2 context-free, L3 recursive and L4 recursively enumerable. List I: (a) complement(L3) ∪ L4, (b) complement(L2) ∪ L3, (c) L1* ∩ L2. List II: (i) Context-free language, (i…
- How can the decision algorithm be constructed L for deciding whether context-free language is finite? CFGG (a) By constructing redundant in CNF L generating language −− (b) By constructing non-redundant CFG G in CNF L g…
- Consider the following grammar : S → XY X → Y aY ∣ a and Y → bbX Which of the following statements is/are true about the above grammar? (a) Strings produced by the grammar can have a consecutive three 's. (b) Every stri…
- Which of the following problems is/are decidable problem(s) (recursively enumerable) on turing M machine ? G L(G) = ϕ (a) is a CFG with M M (b) There exist two TMs 1 and 2 such that L(M) ⊆ {L (M ) ∪ L (M )} = 1 2 langua…
- For a statement L ⊆ Σ∗ A language is recursive if there exists M some turing machine . Which of the following conditions is satisfied for ω any string ? ω ∈ L M ω M
- Let r = a(a + b)*, s = aa*b and t = a*b be three regular expressions. Consider: (i) L(s) ⊆ L(r) and L(s) ⊆ L(t) (ii) L(r) ⊆ L(s) and L(s) ⊆ L(t)
- Consider the language L = {a^(nk) | k > 0}, where n is a fixed non-negative integer. The minimum number of states of a finite automaton accepting L is
- The number of substrings that can be formed from a string given by a d e f b g h n m p is
- Consider the languages L₁ = {x | for some y with |y| = 2|x|, xy ∈ L} and L₂ = {x | for some y with |x| = |y|, xy ∈ L}, where L is a regular language. Which one is correct?
- Consider L₁ = {a^(n+m) bⁿ aᵐ | n, m ≥ 0} and L₂ = {a^(n+m) b^(n+m) a^(n+m) | n, m ≥ 0}. Which one is correct?
- Consider to be any regular language and L , L 1 2 be any two context-free languages. Which one of the following is correct?
- Consider the following problems : (i) Whether a finite state automaton halts on all inputs ? (ii) Whether a given context free language is regular? (iii) Whether a Turing machine computes the product of two numbers? Whi…
- Which of the following problems is decidable for recursive languages L?
- Consider the grammar G: S → A | B, A → a | c, B → b | c, with non-terminals {S, A, B} and terminals {a, b, c}. S₁: LR(1) can parse all strings generated by G. S₂: LL(1) can parse all strings generated by G.
- The grammar S → (S) | SS | ε is not suitable for predictive parsing because the grammar is