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

If the regular set $$A$$ is represented by $$A = {\left( {01 + 1} \right)^ * }$$ and the regular set $$'B'$$ is represented by $$B = \left( {{{\left( {01} \right)}^ * }{1^ * }} \right),$$ which of the following is true?

$$A \subset B$$

$$B \subset A$$

$$A$$ and $$B$$ are incomparable

$$A=B$$

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\}.$$