GATE CSE 2000 | Finite Automata and Regular Language Question 89 | 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

A finite state machine with the following state table has a single input $$X$$ and a single out $$Z$$. GATE CSE 1995 Theory of Computation - Finite Automata and Regular Language Question 83 English

GATE CSE 1995 Theory of Computation - Finite Automata and Regular Language Question 83 English

If the initial state is unknown, then the shortest input sequence to reach the final state $$C$$ is here, since initial make unknown $$m$$ $$10$$ input we can each final state $$C$$ with shortest path.

$$01$$

$$10$$

$$101$$

$$110$$

PREVIOUS NEXT