GATE CSE 2000 | GATE CSE Year Wise Previous Years Questions

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

2024