GATE CSE 2012 | Finite Automata and Regular Language Question 48 | Theory of Computation

GATE CSE 2012

MCQ (Single Correct Answer)

-0.3

What is the complement of the language accepted by the $$NFA$$ shown below?
Assume $$\sum { = \left\{ a \right\}\,\,} $$ and $$\varepsilon $$ is the empty string. GATE CSE 2012 Theory of Computation - Finite Automata and Regular Language Question 87 English

GATE CSE 2012 Theory of Computation - Finite Automata and Regular Language Question 87 English

$$\phi $$

$$\left\{ \varepsilon \right\}$$

$$a{}^ * $$

$$\left\{ {a,\,\,\varepsilon } \right\}$$

GATE CSE 2010

MCQ (Single Correct Answer)

-0.3

Let $${L_1}$$ recursive language. Let $${L_2}$$ and $${L_3}$$ be languages that are recursively enumerable but not recursive. Which of the following statement is not necessarily true?

$${L_2}$$ $$-$$ $${L_1}$$ is recursively enumerable.

$${L_1}$$ $$-$$ $${L_3}$$ recursively enumerable.

$${L_2} \cap {L_1}$$ is recursively enumerable.

$${L_2} \cup {L_1}$$ is recursively enumerable.

GATE CSE 2009

MCQ (Single Correct Answer)

-0.3

Which one of the following languages over the alphabet $$\left\{ {0,\left. 1 \right)} \right.$$ is described by the regular expression $${\left( {0 + 1} \right)^ * }0{\left( {0 + 1} \right)^ * }0{\left( {0 + 1} \right)^ * }$$

The set of all strings containing the substring $$00$$

The set of all strings containing at most two $$0’$$s

The set of all strings containing at least two $$0’$$s

The set of all strings that begin and end with either $$0$$ or $$1$$

GATE CSE 2003

MCQ (Single Correct Answer)

-0.3

The regular expression $${0^ * }\left( {{{10}^ * }} \right){}^ * $$denotes the same set as

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

$$0 + \left( {0 + 10} \right){}^ * $$

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

None of the above.