Question

Let L be the language represented by the regular expression ${\sum }^{\ast }0011{\sum }^{\ast }$ where $\sum =\{0,1\}$. What is the minimum number of states in a DFA that recognizes $\overline{L}$ (complement of L) ?

Answer 1

${\sum }^{\ast }0011{\sum }^{\ast }=(0+1{)}^{\ast }0011(0+1{)}^{\ast }$

Every string of the language L contains the substring 0011.

To accept the minimal string "0011" we need 5 states. Since substring machines don't required trap state, we need only 5 states.

Since the complementary DFA will accept complementary language, and since complementary DFA has same number of states

as the original DFA, therefore $\overline{L}$ also has only 5 states as shown below.

Minimized DFA for

Minimized DFA for