GATE CSE 2005 | GATE CSE Year Wise Previous Years Questions

GATE CSE

GATE CSE 2005

MCQ (Single Correct Answer)

-0.6

Let $${N_f}$$ and $${N_p}$$ denote the classes of languages accepted by non-deterministic finite automata and non-deterministic push-down automata, respectively. Let $${D_f}$$ and $${D_p}$$ denote the classes of languages accepted by deterministic finite automata and deterministic push-down automata, respectively. Which one of the following is TRUE?

$${D_f} \subset {N_f}$$ and $${D_P} \subset {N_p}$$

$${D_f} \subset {N_f}$$ and $${D_P} = {N_p}$$

$${D_f} = {N_f}$$ and $${D_P} = {N_p}$$

$${D_f} = {N_f}$$ and $${D_P} \subset {N_p}$$

GATE CSE 2005

MCQ (Single Correct Answer)

-0.6

Consider the machine $$M:$$ The language recognized by $$M$$ is: GATE CSE 2005 Theory of Computation - Finite Automata and Regular Language Question 42 English

GATE CSE 2005 Theory of Computation - Finite Automata and Regular Language Question 42 English

$$\left\{ {w\,\, \in \,\left\{ {a,b} \right\}{}^ * \left| \, \right.} \right.$$ every $$a$$ in $$w$$ is followed by exactly two $$\left. {b's} \right\}$$

$$\left\{ {w\,\, \in \,\left\{ {a,b} \right\}{}^ * \left| \, \right.} \right.$$ every $$a$$ in $$w$$ is followed by at least two $$\left. {b's} \right\}$$

$$\left\{ {w\,\, \in \,\left\{ {a,b} \right\}{}^ * \left| \, \right.} \right.$$ $$w$$ contains the substring $$\,\left. {'abb'\,\,} \right\}\,$$

$$\left\{ {w\,\, \in \,\left\{ {a,b} \right\}{}^ * \left| \, \right.} \right.$$ $$w$$ does not contain $$'aa'$$ as a substring$$\left. \, \right\}$$

GATE CSE Papers

2024