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, j if you are at position i on the number line, you may directly move to j. Suppose T(k) denotes the smallest number of steps needed to move from k to 100. Suppose further that there is at most 1 shortcut involving any number, and in particular from 9 there is a shortcut to 15. Let y and z be such that T(9) = 1 + min(T(y),T(z)). Then the value of the product yz is _____. [GATE – 2014]
a. 150
b. 151
c. 152
d. 153
Answer : a)
- Consider the following languages over the alphabet Σ = {0,1, c}:
Here, wris the reverse of the string . Which of these languages are deterministic Context-free languages? [GATE – 2014]
a. None of the languages
b. Only L1
c. Only L1 and L2
d. All the three languages
Answer: c)
- Consider the decision problem 2CNFSAT defined as follows:
The decision problem 2CNFSAT is : [GATE – 2014]
a. NP-Complete.
b. solvable in polynomial time by reduction to directed graph reachability.
c. solvable in constant time since any input instance is satisfiable.
d. NP-hard, but not NP-complete.
Answer : b)
- Which one of the following problems is undecidable? [GATE – 2014]
a. Deciding if a given context-free grammar is ambiguous.
b. Deciding if a given string is generated by a given context-free grammar.
c. Deciding if the language generated by a given context-free grammar is empty.
d. Deciding if the language generated by a given context-free grammar is finite.
Answer : a)
- Let Σ be a finite non-empty alphabet and let 2Σ* be the power set of Σ*. Which one of the following is TRUE? [GATE – 2014]
a. Both 2Σ* and Σ* are countable
b. 2Σ* is countable and Σ* is uncountable
c. 2Σ* is uncountable and Σ* is countable
d. Both 2Σ* and Σ* are uncountable
Answer : c)
- The length of the shortest string NOT in the language (over Σ = {a b,} of the following regular is expression is ______________. a*b*(ba)*a* [GATE – 2014]
a. 3
b. 4
c. 5
d. 6
Answer : a)
- Let L1 = {w ∈ {0,1}* | w has at least as many occurrences of (110)’s as (011)’s}. Let L2 = {w ∈ {0,1}*|w has at least as many occurrences of (000)’s as (111)’s}. Which one of the following is TRUE? [GATE – 2014]
a. L2 is regular but not L1
b. L1 is regular but not L2
c. Both L1 and L2 are regular
d. Neither nor L1 are L2 regular
Answer: b)
- Let <M> be the encoding of a Turing machine as a string over Σ = {0, 1} Let L = {<M> |M is a Turing machine that accepts a string of length 2014}. Then, L is : [GATE – 2014]
a. decidable and recursively enumerable
b. undecidable but recursively enumerable
c. undecidable and not recursively enumerable
d. decidable but not recursively enumerable
Answer : b)
TOC |Gate-2014|
- Let A≤mB denotes that language A is mapping reducible (also known as many-to-one reducible) to language B. Which one of the following is FALSE? [GATE – 2014]
a. If A≤m B and B is recursive then A is recursive.
b. If A≤m Band A is undecidable then B is undecidable.
c. If A≤m Band B is recursively enumerable then A is recursively enumerable.
d. If A≤m B and B is not recursively enumerable then A is not recursively enumerable.
Answer : d)
- Which one of the following is TRUE? [GATE – 2014]
a. The language L={an bn│n≥0} is regular.
b. The language L={an│n is prime} is regular.
c. The language L={w│w has 3k+1b’s for some k∈N with Σ={a,b} } is regular
d. The language L={ww│w∈Σ* with Σ={0,1} } is regular.
Answer : c)
TOC |Gate-2014|