# TOC |Gate-2014| Previous Year Questions| Set-7 TOC |Gate-2014| Theory of Computation ( Automata)

1. 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

1. 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

1. 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.

1. 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.

1. 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

1. 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

1. 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

1. 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

TOC |Gate-2014|

1. 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.

1. 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.