GATE CSE 2016 Set 2 | Finite Automata and Regular Language Question 35 | Theory of Computation

GATE CSE 2016 Set 2

MCQ (Single Correct Answer)

-0.3

Language $${L_1}$$ is defined by the grammar: $$S{}_1 \to a{S_1}b|\varepsilon $$
Language $${L_2}$$ is defined by the grammar: $$S{}_2 \to ab{S_2}|\varepsilon $$

Consider the following statements:
$$P:$$ $${L_1}$$ is regular
$$Q:$$ $${L_2}$$ is regular

Which one of the following is TRUE?

Both $$P$$ and $$Q$$ are true

$$P$$ is true and $$Q$$ is false

$$P$$ is false and $$Q$$ is true

Both $$P$$ and $$Q$$ are false

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 2015 Set 3

MCQ (Single Correct Answer)

-0.3

Let $$L$$ be the language represented by the regular expression $$\sum {^ * 0011\sum {^ * } } $$ where $$\sum { = \left\{ {0,1} \right\}} .$$ What is the minimum number of states in a $$DFA$$ that recognizes $$\overline L $$ (complement of $$L$$)?

$$4$$

$$5$$

$$6$$

$$8$$

GATE CSE 2014 Set 3

Numerical

-0

The length of the shortest string NOT in the language (over $$\sum { = \left\{ {a,\,\,b} \right\}} $$) of the following regular expression is ____________. $$$a{}^ * b{}^ * \left( {ba} \right){}^ * a{}^ * $$$

Your input ____