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$
5
  • 2
    $\begingroup$ en.wikipedia.org/wiki/Brzozowski_derivative $\endgroup$
    – Pseudonym
    Jan 22 at 1:28
  • 1
    $\begingroup$ Where are you learning automata theory from, that they led with "just have fun with it" instead of "Here are the Thompson construction rules, and here's how to convert a NFA into a DFA"?? It was years before I realized anybody did anything other than the boring plug-and-chug constructions. $\endgroup$
    – Sneftel
    Jan 22 at 11:04
  • 2
    $\begingroup$ Whilst the process of converting a regex to a DFA is deterministic, the decision about whether to do so is a matter of judgement. Judgement is also something that can be done systematically, although it is hard to get right. blog.burntsushi.net/regex-internals is written by the maintainer of a regex library, and gives some insight into what this looks like in practice. $\endgroup$
    – James_pic
    Jan 22 at 11:21
  • $\begingroup$ Thanks for these amazing answers. @Sneftel It's from a uni course. $\endgroup$ Jan 22 at 13:35
  • $\begingroup$ Converting a regex to a DFA is "just a matter of judgement" in the same sense that it's a matter of judgement how to calculate 13+14+17: you are free to convert it to 27+17 or to 10+14+20 or to 3x15-2-1+2 or use any other method of your choosing. But there do exist systematic algorithms to perform addition, and no matter what method you use, you'll get expressions of the same number. $\endgroup$
    – Stef
    Jan 22 at 19:26

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
    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
    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.