I have to provide a DFA for the following langage: $L=\{w|w$ is any string not in $a^*b^*\}$

For this problem, I think I have to use the complement; however, I don't clearly understand what $a^*b^*$ stands for. I think it's just all the strings in the form:


by the way, I don't know if * includes the empty character.


Let's do the complement of the given language first

Transition function:

\begin{array}{|c|c|} \hline & a & b \\ \hline q_0&q_1 &q_3 \\ \hline q_1&q_1&q_2\\ \hline q_2&q_4 &q_2 \\ \hline q_3&q_4 &q_3 \\ \hline q_4&q_4 &q_4 \\ \hline \end{array}

Start state={$q_0$}
Accept states={$q_0,q_1,q_2,q_3$}

so the automata for the initial language is the same as the previous but it differs in the accept states

Accept states={$q_4$}

  • $\begingroup$ Yes, the $*$ includes the empty string. So your understanding of $a^{*}b^{*}$ seems to be correct -- it's all strings where first we have some (or none) of $a$'s followed by some (or none) of $b$'s. $\endgroup$ – zipirovich Jan 27 '17 at 5:41
  • $\begingroup$ I will provide the desired automata in a 5 tuple to see if it's right. $\endgroup$ – TheMathNoob Jan 27 '17 at 5:43
  • $\begingroup$ @zipirovich I posted the solution $\endgroup$ – TheMathNoob Jan 27 '17 at 5:57
  • $\begingroup$ It looks good and correct to me. Although I think that it can be simplified by combining states $q_3$ and $q_2$. $\endgroup$ – zipirovich Jan 28 '17 at 23:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.