<p>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.</p>
<p>Checking if a regular expression represents the language containing all strings is a PSPACE complete problem (see <a href="https://cstheory.stackexchange.com/a/14954/4155">this answer</a> 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.</p>
<p>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.</p>
<p>There has been a lot of work on identifying sub-families of regular expressions from which we can <em>efficiently</em> 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.</p>
<p>The standard construction of automata from regular expressions is <em>not the preferred construction</em> 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 <em>derivative</em> of a regular expression.</p>
<blockquote>
<p><a href="http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=3385747B5A9A642D7063785A49CD87FD?doi=10.1.1.98.4378&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">Derivatives of regular expressions</a>, J. A. Brzozowski. 1964.</p>
</blockquote>
<p>A derivative <span class="math-container">$s$</span> of a regular expression <span class="math-container">$r$</span> with respect to a symbol <span class="math-container">$a$</span> from the alphabet is a regular expression representing the language of <span class="math-container">$r$</span> with the leading <span class="math-container">$a$</span> removed from strings. This notion was extended to partial derivatives of regular expressions by Antimirov.</p>
<blockquote>
<p><a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.56.2509&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">Partial Derivatives of Regular Expressions and Finite Automata Constructions</a>, V. Antimirov. 1995.</p>
</blockquote>
<p>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 <em>states</em>. Contrast with the standard textbook construction which intuitively treats regular expressions as automata, not states.</p>
<blockquote>
<p><a href="https://doi.org/10.1016/0304-3975(86)90088-5" rel="nofollow noreferrer">From regular expressions to deterministic automata</a>, G. Berry and R. Sethi, 1986.</p>
</blockquote>
<p>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.</p>
<blockquote>
<p><a href="http://www.cs.ust.hk/%7Edwood/preprints/infcomp.ps.gz" rel="nofollow noreferrer">One-Unambiguous Regular Languages</a>, A. Brüggemann-Klein and Derick Wood, 1998.</p>
</blockquote>
<p>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.</p>
<p>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.</p>
<blockquote>
<p><a href="https://hal.inria.fr/inria-00618451" rel="nofollow noreferrer">Deterministic Regular Expressions in Linear Time</a>, Benoit Groz, Sebastian Maneth, Slawomir Staworko. 2012.</p>
</blockquote>

CC BY-SA 3.0
2013-01-03T08:44:08.137Z
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.
Neel Krishnaswami
CC BY-SA 3.0
2013-01-03T08:51:59.770Z
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?
Vijay D
CC BY-SA 3.0
2013-01-04T08:07:00.080Z
If you have the time and energy, I think longish survey-like answers are very appropriate here.
David Eppstein
CC BY-SA 3.0
2013-01-04T09:32:44.840Z
@VijayD: yeah, I agree with David. Short answers are fine, but if you have the energy it's nice to give a comprehensive answer.
Neel Krishnaswami
CC BY-SA 4.0
2013-01-03T08:21:23.337Z
2022-06-03T11:15:00.850Z
2022-06-03T11:15:00.850Z
Vijay D
<p>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?</p>

<automata-theory><regular-expressions><dfa>
What algorithms exist for construction a DFA that recognizes the language described by a given regex?
BlueBomber
# What algorithms exist for construction a DFA that recognizes the language described by a given regex?

(Asked by: username_0 on 2013-01-03)

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?

**Tags:** automata-theory, regular-expressions, dfa


---

## 1 answers

### Answer by username_1 on 2013-01-03. Score: 16 | Accepted answer

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](https://cstheory.stackexchange.com/a/14954/4155) 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](http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=3385747B5A9A642D7063785A49CD87FD?doi=10.1.1.98.4378&rep=rep1&type=pdf), 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](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.56.2509&rep=rep1&type=pdf), 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](https://doi.org/10.1016/0304-3975(86)90088-5), 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](http://www.cs.ust.hk/%7Edwood/preprints/infcomp.ps.gz), 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](https://hal.inria.fr/inria-00618451), Benoit Groz, Sebastian Maneth, Slawomir Staworko. 2012.

> **Comments:**
> **username_2**: 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.  
> **username_1**: 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?  
> **username_3**: If you have the time and energy, I think longish survey-like answers are very appropriate here.  
> **username_2**: @VijayD: yeah, I agree with David. Short answers are fine, but if you have the energy it's nice to give a comprehensive answer.  

---

