0
$\begingroup$

I'm trying to come up with an alternate DFA for accepting (a|b)*abb than the one present in the dragon book. Here's the one I tried:

Alternative DFA accepting strings that match regex (a|b)*abb

It seems valid to me but I'm not sure. Also, is there a way to check for validity of automatons so that I don't end up bugging you guys next time?

$\endgroup$
  • 1
    $\begingroup$ Given two DFAs, you can check whether they accept the same language via the product automaton. There might even be libraries implementing this algorithm. $\endgroup$ – Yuval Filmus Apr 9 at 17:33
  • 1
    $\begingroup$ Your DFA does not accept $a b b$, which is part of your language (shortest accepted strings are $a a b b$ and $b a b b$), $\endgroup$ – vonbrand Apr 13 at 1:51
  • 1
    $\begingroup$ @YuvalFilmus, or build minimal automata for each, and compare. Look at e.g. JFLAP or Automata Tutor for some easy to use tools to fool around with automata (not just finite ones). $\endgroup$ – vonbrand Apr 13 at 1:54
2
$\begingroup$

Your DFA does not recognize $(a|b)^*abb$. For example it does not recognize $abb$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Yep! It doesn't. Thanks :^) $\endgroup$ – Devashish Jaiswal Apr 9 at 17:40

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.