GATE CSE 2014 Set 1 | Finite Automata and Regular Language Question 28 | Theory of Computation

GATE CSE 2014 Set 1

MCQ (Single Correct Answer)

-0.3

Consider the finite automation in the following figure. GATE CSE 2014 Set 1 Theory of Computation - Finite Automata and Regular Language Question 68 English

GATE CSE 2014 Set 1 Theory of Computation - Finite Automata and Regular Language Question 68 English

What is the set of reachable states for the input string $$0011?$$

$$\left\{ {{q_0},\,{q_1},\,{q_2}} \right\}$$

$$\left\{ {{q_0},\,{q_1}} \right\}$$

$$\left\{ {{q_0},\,{q_1},\,{q_2},\,{q_3}} \right\}$$

$$\left\{ {{q_3}} \right\}$$

GATE CSE 2013

MCQ (Single Correct Answer)

-0.3

Consider the languages $${L_1} = \phi $$ and $${L_2} = \left\{ a \right\}.$$ Which one of the following represents $${L_1}\,L_2^ * UL_1^ * ?$$

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

$$\phi $$

$${a^ * }$$

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

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

GATE CSE 2012 Theory of Computation - Finite Automata and Regular Language Question 71 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.

PREVIOUS NEXT