# What algorithms exist for construction a DFA that recognizes the language described by a given regex?

All of my textbooks use the same algorithm for producing a DFA given a regex: First, make an NFA that recognizes the language of the regex, then, using the subset (aka "powerset") construction, convert the NFA into an equivalent DFA (optionally minimizing the DFA). I also once heard a professor allude to there being other algorithms. Does anyone know of any? Perhaps one that goes directly from the regex to a DFA without the intermediate NFA?

There are different algorithms to convert regular expressions to finite automata. You can go directly from regular expressions to DFAs without building any other automaton first by implicitly doing the subset construction while generating the automaton. Another option to directly obtain deterministic automata is to use the method of derivatives.

Checking if a regular expression represents the language containing all strings is a PSPACE complete problem (see this answer for a reference). Checking if a DFA accepts that language can be done in polynomial time, so if you go directly from a regular expression to a DFA, there will be a blow-up somewhere.

My understanding of the literature is that we can choose translations that allow us to localise the blow-up. Meaning, there are different ways to go from a regular expression to a finite automaton, and methods that are linear, or polynomial are preferred. Usually, the exponential costs are pushed into determinization of automata.

There has been a lot of work on identifying sub-families of regular expressions from which we can efficiently generate DFAs. This line of work is dependent on the translation you use. Meaning, you fix a mapping from regular expressions to NFAs and try to characterise the regular expressions which map to DFAs.

The standard construction of automata from regular expressions is not the preferred construction in such work. The constructions of choice produce automata which closely resemble the structure of the regular expression. These constructions use the notion of a derivative of a regular expression.

Derivatives of regular expressions, J. A. Brzozowski. 1964.

A derivative $$s$$ of a regular expression $$r$$ with respect to a symbol $$a$$ from the alphabet is a regular expression representing the language of $$r$$ with the leading $$a$$ removed from strings. This notion was extended to partial derivatives of regular expressions by Antimirov.

Partial Derivatives of Regular Expressions and Finite Automata Constructions, V. Antimirov. 1995.

If you think of a state of an automaton as a representation of all strings accepted from that state, (partial) derivatives allow you to treat regular expressions as states. Contrast with the standard textbook construction which intuitively treats regular expressions as automata, not states.

From regular expressions to deterministic automata, G. Berry and R. Sethi, 1986.

The correspondence between regular expressions and states of an automaton and determinism is discussed explicitly by Berry and Sethi, who combine the notion of Brzozowski derivatives with the idea of distinguishing between occurrences of the same symbol to give a syntax-based translation of regular expressions into finite automata.

One-Unambiguous Regular Languages, A. Brüggemann-Klein and Derick Wood, 1998.

This paper builds on earlier work by Brüggemann-Klein and studies cases in which you can use derivatives to generate DFAs in polynomial time. There is a large amount of work following this paper. It was significant from the perspective of web technologies because regular expressions that can be manipulated efficiently (aka, corresponding to DFAs) were important for processing SGML and XML.

There has been much work studying other special cases of deterministic regular expressions. A very recent paper studying when some of these problems can be solved in linear time is from 2012.

Deterministic Regular Expressions in Linear Time, Benoit Groz, Sebastian Maneth, Slawomir Staworko. 2012.

• You've already mentioned derivatives in your answer, so you should also add J. A. Brzozowski: Derivatives of regular expressions, Journal of the ACM 11(4): 481–494 (1964), since he gives a direct algorithm for converting regexps to DFAs. Jan 3, 2013 at 8:44
• I debated about that. But all three papers above directly build on that result, so I thought there was no reason to mention it. The Brueggeman-Klein and Wood paper is full of examples too. If I mention Brzozowski, I feel Antimirov should be mentioned too. I wanted to avoid a survey, but maybe I should just go for it. What say? Jan 3, 2013 at 8:51
• If you have the time and energy, I think longish survey-like answers are very appropriate here. Jan 4, 2013 at 8:07
• @VijayD: yeah, I agree with David. Short answers are fine, but if you have the energy it's nice to give a comprehensive answer. Jan 4, 2013 at 9:32