I want to draw a DFA from the below language:

The set of strings in $\{a, b\}$ where every $a$ is immediately followed by $b$

I can write the regular expression for this language as so:


How do I draw the DFA for this expression?

  • $\begingroup$ In general, the procedure is to draw a non-deterministic finite automaton from the regular expression, then convert to a DFA (where the states consist of set of states of the NDFA). $\endgroup$ – Daniel Schepler Oct 21 '17 at 0:42

I hope it can help you

Language consist of :

  • $\epsilon$
  • strings of just b's
  • and strings such that every a is immediately followed by b $$L=\{\epsilon,b,bb,bbb,...,ab,abb,....,bab,bbababb,.... \}$$ Regular expression: $(b^*\,ab\, b^*)^*+b^*$

DFA that accepts L :

enter image description here

  • $\begingroup$ Very nice! Just out of curiosity: what software did you use to draw the diagram? $\endgroup$ – zipirovich Oct 21 '17 at 18:08
  • $\begingroup$ Thanks @zipirovich :) I used FSM Designer (madebyevan.com/fsm) Created by Evan Wallace $\endgroup$ – W.R.P.S Oct 21 '17 at 18:30

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.