$\begingroup$
$\endgroup$
1
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?
2 Answers
$\begingroup$
$\endgroup$
2
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 :
$\begingroup$
$\endgroup$
1
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.
