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

GATE CSE 2016 Set 1

MCQ (Single Correct Answer)

-0.3

Which one of the following regular expressions represents the language: the set of all binary strings having two consecutive $$0s$$ and two consecutive $$1s?$$

$$\left( {0 + 1} \right){}^ * 0011\left( {0 + 1} \right){}^ * + \left( {0 + 1} \right){}^ * 1100\left( {0 + 1} \right){}^ * $$

$$\left( {0 + 1} \right){}^ * \left( {00\left( {0 + 1} \right){}^ * 11 + 11\left( {0 + 1} \right){}^ * \left. {00} \right)} \right.\left( {0 + 1} \right){}^ * $$

$$\left( {0 + 1} \right){}^ * 00\left( {0 + 1} \right){}^ * + \left( {0 + 1} \right){}^ * 11\left( {0 + 1} \right){}^ * $$

$$00\left( {0 + 1} \right){}^ * 11 + 11\left( {0 + 1} \right){}^ * 00$$

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 40 English

GATE CSE 2016 Set 1 Theory of Computation - Finite Automata and Regular Language Question 40 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

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

Indian currency notes show the denomination indicated in at least seventeen languages. If this is not an indication of the nation’s diversity, nothing else is. Which of the following can be logically inferred from the above sentences?

India is a country of exactly seventeen languages.

Linguistic pluralism is the only indicator of a nation’s diversity.

Indian currency notes have sufficient space for all the Indian languages.

Linguistic pluralism is strong evidence of India’s diversity.

PREVIOUS NEXT

GATE CSE Papers

All year-wise previous year question papers

2026