GATE CSE 2000 | Finite Automata and Regular Language Question 78 | Theory of Computation

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 1998

MCQ (Single Correct Answer)

-0.6

Let $$L$$ be the set of all binary strings whose last two symbols are the same. The number of states in the minimum state deterministic finite-state automaton accepting $$L$$ is

$$2$$

$$5$$

$$8$$

$$3$$

GATE CSE 1997

MCQ (Single Correct Answer)

-0.6

Which one of the following regular expressions over $$\left\{ {0,\,\,1} \right\}$$ denotes the set of all strings not containing $$100$$ as substring?

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

$${0^ * }\,\,{1010^ * }$$

$${0^ * }\,\,{1^ * }\,\,{01^ * }$$

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

GATE CSE 1995

MCQ (Single Correct Answer)

-0.6

Which of the following definitions below generates the same language as $$L$$
Where $$L = {\left\{ x \right.^n}{y^n}\left| {n \ge \left. 1 \right\}} \right.$$
i) $$\,\,E \to xEy\left| {xy} \right.$$
ii) $$\,\,xy\left| {\left( {{x^ + }xy{y^ + }} \right)} \right.$$
iii) $${\,\,{x^ + }{y^ + }}$$
$$L = \left\{ {xn\,{y^n}\left| {n \ge 1} \right.} \right\} - $$ generates string where equal no. of $$x$$ and equal no. of $$y's.$$
$$E \to XBy\left| {xy\,abo} \right.$$ generators tips same.

(i) only

(i) and (ii)

(ii) and (iii)

(ii) only

PREVIOUS NEXT