# How do you draw a DFA from a regular expression?

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:

$$((b^*)(ab)(b^*))^*$$

How do I draw the DFA for this expression?

• 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). Commented Oct 21, 2017 at 0:42
• cs.stackexchange.com/q/165159/755
– D.W.
Commented Jun 20 at 17:53

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 :

• Very nice! Just out of curiosity: what software did you use to draw the diagram? Commented Oct 21, 2017 at 18:08
• Thanks @zipirovich :) I used FSM Designer (madebyevan.com/fsm) Created by Evan Wallace Commented Oct 21, 2017 at 18:30

You can do it on-line using https://cyberzhg.github.io/toolbox/nfa2dfa easily. For your particular example, it gives

You can find a more precise algorithm in the chapter 2 of Modern Compiler Implementation in C, which includes this figure:

How you convert your obtained NFA into a DFA is then fairly standard.

• Underrated answer Commented Feb 14, 2022 at 18:08