11
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Welcome to cstheory, a Q&A site for research-level questions in theoretical computer science (TCS). Your question does not appear to be a research-level question in TCS. Please see the FAQ for more information on what is meant by this. Your question might be suitable for Computer Science which has a broader scope. $\endgroup$ – Kaveh Jan 3 '13 at 7:12
  • 1
    $\begingroup$ why do you always use this template comment ? Apparently there are at least 5 who dont agree with you. I would suggest you give such questions a chance. $\endgroup$ – AJed Jan 3 '13 at 22:05
  • $\begingroup$ @AJed, I don't always use this comment. I use it when a question seems off-topic to me but might be suitable for Computer Science. Up votes does not mean a question is on-topic, and this one doesn't seem to be a research-level question to me, so I think the comment is appropriate. (The fact the someone can write a research-level answer to a question does not make the question research-level.) ps: I think this discussion is more suitable for Theoretical Computer Science Meta. $\endgroup$ – Kaveh Jan 4 '13 at 5:23
13
$\begingroup$

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.

$\endgroup$
  • 5
    $\begingroup$ 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. $\endgroup$ – Neel Krishnaswami Jan 3 '13 at 8:44
  • 3
    $\begingroup$ 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? $\endgroup$ – Vijay D Jan 3 '13 at 8:51
  • 5
    $\begingroup$ If you have the time and energy, I think longish survey-like answers are very appropriate here. $\endgroup$ – David Eppstein Jan 4 '13 at 8:07
  • 1
    $\begingroup$ @VijayD: yeah, I agree with David. Short answers are fine, but if you have the energy it's nice to give a comprehensive answer. $\endgroup$ – Neel Krishnaswami Jan 4 '13 at 9:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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