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

GATE CSE 2000

MCQ (Single Correct Answer)

-0.3

Let $$L$$ denote the language generated by the grammar $$S \to 0S\left. 0 \right|00.$$ Which one of the following is true?

$$L = {0^ + }$$

$$L$$ is regular but not $${0^ + }$$

$$L$$ is context free but not regular

$$L$$ is not context free

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 1999

MCQ (Single Correct Answer)

-0.3

Consider the regular expression $$(0+1)(0+1).......n$$ times. The minimum state finite automation that recognizes the language represented by this regular expression contains:

$$n$$ states

$$n+1$$ states

$$n+2$$ states

None of the above

GATE CSE 1998

MCQ (Single Correct Answer)

-0.3

Which of the following sets can be recognized by a Deterministic Finite-state Automation?

The numbers $$1, 2, 4, 8, $$ ...... $${2^n},$$ ............. written in binary.

The numbers $$1, 2, 4, ..... $$ $${2^n},$$ $$.....$$ written in unary.

The set of binary strings in which the numbers of zeros is the same as the numbers of ones.

The set $$\left\{ {1,101,11011,1110111,...} \right\}.$$