Converting Regex to DFA

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?

• en.wikipedia.org/wiki/Brzozowski_derivative Jan 22 at 1:28
• 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. Jan 22 at 11:04
• 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. Jan 22 at 11:21
• Thanks for these amazing answers. @Sneftel It's from a uni course. Jan 22 at 13:35
• 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.
– Stef
Jan 22 at 19:26

2 Answers

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.

• For me Thompson's construction (en.wikipedia.org/wiki/Thompson%27s_construction) is easier to understand and implement then Glushkov's one.
– ufok
Jan 22 at 6:25
• @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. Jan 22 at 8:36

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.