The following DFA accepts the set of all strings over {0,1} that

2009

The following DFA accepts the set of all strings over {0,1} that

image.png

  1. A.

    Begin either with 0 or 1

  2. B.

    End with 0

  3. C.

    End with 00

  4. D.

    Contain the substring 00

Attempted by 104 students.

Show answer & explanation

Correct answer: C

The DFA starts at the initial state, looping on '1' to ignore leading ones. A transition on '0' moves to an intermediate state, indicating the last character was a single zero. If another '0' is read, it reaches the accepting state; otherwise, a '1' resets to the start. The final state loops on '0', ensuring any subsequent zeros maintain acceptance. Thus, it accepts strings ending with two consecutive zeros.

A video solution is available for this question — log in and enroll to watch it.

Explore the full course: Gate Guidance By Sanchit Sir