GATE CSE 2000 | GATE CSE Year Wise Previous Years Questions

GATE CSE 2000

MCQ (Single Correct Answer)

-0.3

Let $$S$$ and $$T$$ be languages over $$\sum { = \left\{ {a,b} \right\}} $$ represented by the regular expressions $${\left( {a + {b^ * }} \right)^ * }$$ and $$\,{\left( {a + b} \right)^ * },$$ respectively. Which of the following is true?

$$S \subset T$$

$$T \subset S$$

$$S=T$$

$$S \cap T = \phi $$

GATE CSE 2000

MCQ (Single Correct Answer)

-0.6

What can be said about a regular language $$L$$ over $$\left\{ a \right\}$$ whose minimal finite state automation has two states?

Must be $$\left\{ {{a^n}\left| n \right.\,\,} \right.$$ is odd $$\left. \, \right\}$$

Must be $$\left\{ {{a^n}\left| n \right.\,\,} \right.$$ is even $$\left. \, \right\}$$

Must be $$\left\{ {{a^n}\left| {n \ge } \right.\,\,} \right.0\left. \, \right\}$$

Either $$L$$ must be $$\left\{ {{a^n}\left| n \right.\,\,} \right.$$ is odd$$\left. \, \right\}\,\,$$ or $$L$$ must be $$\left\{ {{a^n}\left| n \right.} \right.$$ is even$$\left. \, \right\}$$

GATE CSE 2000

MCQ (Single Correct Answer)

-0.6

Consider the following decision problems :

$${P_1}$$ Does a given finite state machine accept a given string

$${P_2}$$ Does a given context free grammar generate an infinite number of stings.

Which of the following statements is true?

Both $${P_1}$$ and $${P_2}$$ are decidable

Neither $${P_1}$$ and $${P_2}$$ are decidable

Only $${P_1}$$ is decidable

Only $${P_2}$$ is decidable

GATE CSE Papers

2025