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| 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| 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| 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| 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 …
TOC |Gate-2011| Theory of Computation ( Automata) Consider the languages L1,L2 and L3 as given below. Which of the following statements is NOT TRUE? [GATE – 2011] a. Push Down Automate (PDA) can be used to recognize L1 and L2b. L1 is a regular languagec. All the three languages are context freed. Turing machines can be used …
TOC |Gate-2012| Theory of Computation ( Automata) 1. Consider the set of strings on {0,1} in which, every substring of 3 symbols has at most two zeros. For example, 001110 and 011001 are in the language, but 100010 is not. All strings of length less than 3 are also in the language. A partially completed …
TOC |Gate-2013| Theory of Computation ( Automata) 1. Which of the following is/are undecidable? [GATE – 2013] 1. G is a CFG. Is L(G) = ∅ ?2. G is a CFG. Is L(G) = Σ*?3. M is a Turning machine. Is L(M) regular?4. A is a DFA and N is an NFA. Is L(A) = …
TOC |Gate-2014| Theory of Computation ( Automata) Suppose you want to move from 0 to 100 on the number line. In each step, you either move right by a unit distance or you take a shortcut. A shortcut is simply a pre-specified pair of integers i, j with i < j. Given a shortcut i, …
TOC |Gate-2015| Theory of Computation ( Automata) 1. Which of the following languages are context-free? [GATE – 2015] L1 = {ambnanbm ⎪ m, n ≥ 1}L2 = {ambnambn ⎪ m, n ≥ 1}L3 = {ambn ⎪ m = 2n + 1} a. L1 and L2 onlyb. L1 and L3 onlyc. L2 and L3 onlyd. L3 only Answer : b) 2. Language L1 …