# GAte theory of computation question

## TOC |Gate-2006| Previous Year Questions| Set-15

TOC |Gate-2006| Theory of Computation ( Automata) For S ∈ (0 + 1) * let d(s) denote the decimal value of s (e.g. d(101) = 5). Let L = {s ∈ (0 + 1)* d(s)mod5 = 2 and d(s)mod7 != 4}. Which one of the following statements is true?  [GATE – 2006] a. L is …

## TOC |Gate-2007| Previous Year Questions| Set-14

TOC |Gate-2007| Theory of Computation ( Automata) Which of the following problems is undecidable?  [GATE – 2007] a. Membership problem for CFGs.b. Ambiguity problem for CFGs.c. Finiteness problem for FSAs.d. Equivalence problem for FSAs. Answer : b) Which of the following is TRUE?  [GATE – 2007] a. Every subset of a regular set is regular.b. …

## TOC |Gate-2008| Previous Year Questions| Set-13

TOC |Gate-2008| Theory of Computation ( Automata) Which of the following is true for the language {ap|p is a prime} ?  [GATE – 2008] a. It is not accepted by a Turing Machineb. It is regular but not context-freec. It is context-free but not regulard. It is neither regular nor context-free, but accepted by a Turing machine Answer …

## TOC |Gate-2009| Previous Year Questions| Set-12

TOC |Gate-2009| Theory of Computation ( Automata) S → aSa|bSb|a|b; The language generated by the above grammar over the alphabet {a,b} is the set of : [GATE – 2009] a. All palindromes.b. All odd length palindromes.c. Strings that begin and end with the same symbol.d. All even length palindromes. Answer : b) Which one of …

## TOC |Gate-2010| Previous Year Questions| Set-11

TOC |Gate-2010| Theory of Computation ( Automata) Let L1 be a recursive language. Let L2 and L3 be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true? [GATE – 2010] a. L2 – L1 is recursively enumerableb. L1 – L3 is recursively enumerablec. L2 ∩ L1 is …

## Engineering-Mathematics |Gate-2006| Previous Year Questions| Set-15

Engineering-Mathematics |Gate-2006| The 2n vertices of a graph G corresponds to all subsets of a set of size n, for n >= 6. Two vertices of G are adjacent if and only if the corresponding sets intersect in exactly two elements. The number of connected components in G is: [GATE – 2006] a. nb. n+2c. 2n/2d. …

## Engineering-Mathematics |Gate-2007| Previous Year Questions| Set-14

Engineering-Mathematics |Gate-2007| 1. Consider the following two statements about the function f(x)=|x| P. f(x) is continuous for all real values of xQ. f(x) is differentiable for all real values of x Which of the following is TRUE? [GATE – 2007] a. P is true and Q is falseb. P is false and Q is true.c. …

## Engineering-Mathematics |Gate-2008| Previous Year Questions| Set-13

Engineering-Mathematics |Gate-2008| If P, Q, R are subsets of the universal set U, then (P∩Q∩R) ∪ (Pc∩Q∩R) ∪ Qc ∪ Rc is : [GATE – 2008] a. Qc ∪ Rcb. P ∪ Qc ∪ Rcc. Pc ∪ Qc ∪ Rcd. U Answer : d) The following system of equations x1 + x2  + 2×3  = 1 x1 + 2×2 + 3 x3 = 2 …

## Engineering-Mathematics |Gate-2009| Previous Year Questions| Set-12

Engineering-Mathematics |Gate-2009| Which one of the following is TRUE for any simple connected undirected graph with more than 2 vertices? [GATE – 2009] a. No two vertices have the same degree.b. At least two vertices have the same degree.c. At least three vertices have the same degree.d. All vertices have the same degree. Answer : …

## Engineering-Mathematics |Gate-2010| Previous Year Questions| Set-11

Engineering-Mathematics |Gate-2010| Let G = (V,E) be a graph. Define ξ(G) = Σd id x d, where id is the number of vertices of degree d in G. If S and T are two different trees with ξ(S) = ξ(T),then  : [GATE – 2010] a. |S| = 2|T|b. |S| = |T| – 1c. |S| = …