**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, w^{r}is the reverse of the string . Which of these languages are deterministic Context-free languages? **[GATE – 2014]**

a. None of the languages

b. Only L_{1}

c. Only L_{1} and L_{2}

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 L
_{1}= {w ∈ {0,1}* | w has at least as many occurrences of (110)’s as (011)’s}. Let L_{2}= {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. L_{2} is regular but not L_{1}

b. L_{1} is regular but not L_{2}

c. Both L_{1} and L_{2} are regular

d. Neither nor L_{1} are L_{2} 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≤
_{m}B 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={a^{n} b^{n}│n≥0} is regular.

b. The language L={a^{n}│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|