GATE CSE 2001 | Finite Automata and Regular Language Question 70 | Theory of Computation

GATE CSE 2001

MCQ (Single Correct Answer)

-0.6

Consider the following languages:
$${L_1} = \left\{ {w\,w\left| {w \in {{\left\{ {a,\,b} \right\}}^ * }} \right.} \right\}$$
$${L_2} = \left\{ {w\,{w^R}\left| {w \in {{\left\{ {a,\,b} \right\}}^ * },} \right.{w^R}\,\,} \right.$$ is the reverse of $$\left. w \right\}$$
$${L_3} = \left\{ {{0^{2i}}\left| {i\,\,} \right.} \right.$$ is an integer$$\left. \, \right\}$$
$${L_4} = \left\{ {{0^{{i^2}}}\left| {i\,\,} \right.} \right.$$ is an integer$$\left. \, \right\}$$

Which of the languages are regular?

Only $${L_1}$$ and $${L_2}$$

Only $${L_2},$$ $${L_3}$$ and $${L_4}$$

Only $${L_3}$$ and $${L_4}$$

Only $${L_3}$$

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)^ * }$$

PREVIOUS NEXT