GATE CSE 2016 Set 1 | GATE CSE Year Wise Previous Years Questions

GATE CSE 2016 Set 1

MCQ (Single Correct Answer)

-0.6

Consider the transition diagram of a $$PDA$$ given below with input alphabet $$\sum {\, = \left\{ {a,b} \right\}} $$ and stack alphabet $$\Gamma = \left\{ {X,Z} \right\}.$$ $$Z$$ is the initial stack symbol. Let $$L$$ denote the language accepted by the $$PDA.$$ GATE CSE 2016 Set 1 Theory of Computation - Finite Automata and Regular Language Question 29 English

GATE CSE 2016 Set 1 Theory of Computation - Finite Automata and Regular Language Question 29 English

Which one of the following is TRUE?

$$L = \left\{ {{a^n}{b^n}|n \ge 0} \right\}$$ and is not accepted by any finite automata

$$L = \left\{ {{a^n}|n \ge 0} \right\} \cup \left\{ {{a^n}{b^n}|n \ge 0} \right\}$$ and is not accepted by any deterministic $$PDA$$

$$L$$ is not accepted by any Turing machine that halts on every input

$$L = \left\{ {{a^n}|n \ge 0} \right\} \cup \left\{ {{a^n}{b^n}|n \ge 0} \right\}$$ and is deterministic context-free

GATE CSE 2016 Set 1

MCQ (Single Correct Answer)

-0.6

Consider the following context-free grammars:
$$\eqalign{ & {G_1}:\,\,\,\,\,S \to aS|B,\,\,B \to b|bB \cr & {G_2}:\,\,\,\,\,S \to aA|bB,\,\,A \to aA|B|\varepsilon ,\,\,B \to bB|\varepsilon \cr} $$

Which one of the following pairs of languages is generated by $${G_1}$$ and $${G_2}$$, respectively?

$$\left\{ {{a^m}{b^n}|m > 0\,\,\,\,} \right.$$ or $$\,\,\,\,$$$$n > \left. 0 \right\}$$ and $$\left\{ {{a^m}{b^n}|m > 0\,\,\,\,} \right.$$ and $$\,\,\,\,n > \left. 0 \right\}\,\,\,\,$$

$$\left\{ {{a^m}{b^n}|m > 0\,\,\,\,} \right.$$ and $$\,\,\,n > \left. 0 \right\}\,\,\,\,$$ and $$\left\{ {{a^m}{b^n}|m > 0\,\,\,\,} \right.$$ or $$\,\,\,\,n \ge \left. 0 \right\}$$

$$\left\{ {{a^m}{b^n}|m \ge 0\,\,\,\,} \right.$$ or $$\,\,\,\,n > \left. 0 \right\}\,\,\,\,$$ and $$\left\{ {{a^m}{b^n}|m > 0\,\,\,\,} \right.\,$$ and $$\,\,\,\,n > \left. 0 \right\}\,\,\,\,$$

$$\left\{ {{a^m}{b^n}|m \ge 0\,\,\,\,} \right.$$ and $$\,\,\,n > \left. 0 \right\}\,\,\,\,$$ and $$\left\{ {{a^m}{b^n}|m > 0\,\,\,\,} \right.\,$$ or $$\,\,\,\,n > \left. 0 \right\}\,\,\,\,$$

GATE CSE 2016 Set 1

MCQ (Single Correct Answer)

-0.6

Let $$X$$ be a recursive language and $$Y$$ be a recursively enumerable but not recursive language. Let $$W$$ and $$Z$$ be two languages such that $$\overline Y $$ reduces to $$W,$$ and $$Z$$ reduces to $$\overline X $$ (reduction means the standard many-one reduction). Which one of the following statements is TRUE?

$$W$$ can be recursively enumerable and $$Z$$ is recursive.

$$W$$ can be recursive and $$Z$$ is recursively enumerable.

$$W$$ is not recursively enumerable and $$Z$$ is recursive.

$$W$$ is not recursively enumerable and $$Z$$ is not recursive.

GATE CSE 2016 Set 1

MCQ (Single Correct Answer)

-0.6

In a process, the number of cycles to failure decreases exponentially with an increase in load. At a load of $$80$$ units, it takes $$100$$ cycles for failure. When the load is halved, it takes $$10000$$ cycles for failure. The load for which the failure will happen in $$5000$$ cycles is ________.

$$40.00$$

$$46.02$$

$$60.01$$

$$92.02$$

PREVIOUS NEXT

GATE CSE Papers

2024