How do you draw a DFA from a regular expression?

Question

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?

Answer 1

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 :

Answer 2

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.