2
$\begingroup$

People I know said that converting a Regex to DFA is just a "matter of judgement" (I do not believe them, there has to be a more systematic approach).

Is there a simple/intuitive, yet concise way to convert a Regex like this

a*b+a(b+a|aa+b)*ab(a?|bb?a)+

into a DFA?

$\endgroup$
3

2 Answers 2

7
$\begingroup$

You can convert the regular expression into an automaton using the Glushkov's construction.

The resulting automaton is non-deterministic, but you can find a deterministic automaton using the powerset construction.

However, the resulting automaton could have a size exponential in the size of the regular expression. There is no construction that always gives an automaton with polynomial size. For example, the minimal deterministic automaton that recognizes $(a\mid b)^*a\underbrace{(a\mid b)…(a\mid b)}_{n-1\text{ times}}$ has $2^n$ states.

$\endgroup$
2
  • 3
    $\begingroup$ For me Thompson's construction (en.wikipedia.org/wiki/Thompson%27s_construction) is easier to understand and implement then Glushkov's one. $\endgroup$
    – ufok
    Commented Jan 22 at 6:25
  • 1
    $\begingroup$ @ufok While Thompson's construction may seem easier to understand, the resulting automaton has a size that is double of the number of symbols in the regular expression, while the Glushkov's automaton has a size that is the number of letters (plus one) in the regular expression, so less than half the size of Thompson's. $\endgroup$
    – Nathaniel
    Commented Jan 22 at 8:36
1
$\begingroup$

You can convert a regexp to a DFA with Thompson's algorithm. It is covered in many resources, including standard textbooks on automata theory.

Alternatively, you could consider Glushkov's algorithm. See also what is glushkov NFA. What is the difference between Glushkov NFA and Thompson NFA?.

These convert a regexp to NFA. Then you can use the subset construction to convert the NFA to a DFA.

There are others as well. See, e.g., Bruce W. Watson, A taxonomy of finite automata construction algorithms; Russ Cox's tutorial; and a good textbook on automata theory.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.