Minimum number of states required in DFA accepting binary strings not ending…

2020

Minimum number of states required in DFA accepting binary strings not ending in “101” is , ISRO 2020

  1. A.

    3

  2. B.

    4

  3. C.

    5

  4. D.

    6

Attempted by 144 students.

Show answer & explanation

Correct answer: B

To determine the minimum number of states for a DFA accepting binary strings not ending in '101', we analyze the complementary language of strings ending in '101'. A minimal DFA recognizing a specific suffix pattern of length n requires exactly n+1 states to track the progress through that pattern. Since '101' has a length of 3, the minimal DFA requires 3+1=4 states. The complement machine simply swaps accepting and non-accepting states, maintaining the same total count of 4.

Explore the full course: Isro