1
$\begingroup$

Suppose that we have been given a regular expression $L$ and then we are asked to calculate the minimum number of states in the minimum sized DFA? How can we go about solving such questions?

What I thought is that first we need to convert the given regular expression to The DFA and then minimise it.

Is there any better way which can directly give the number of states or even the minimised DFA? The way I follow becomes sometimes very tough as it depends whether the expression at hand is an easy one or a tough one. Is there some general algorithm or some lemma which might come in handy in order to answer such questions?

(This is supposed to be a reference question. Please include a general description of your method as well as a non-trivial example.)

| cite | improve this question | | | | |
$\endgroup$