How do you draw a DFA from a regular expression?

$\begingroup$

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?

$\endgroup$ 1

2 Answers

$\begingroup$

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 :

$\endgroup$ 2 $\begingroup$

You can do it on-line using 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.

$\endgroup$ 1