5
$\begingroup$

It's well known that a regular expression can be converted to a non-deterministic finite state automaton, which can in turn be converted in to a deterministic finite state automaton. These DFAs can then be compiled directly into code as in e.g. re2c.

However, most libraries for regular expressions allow for captures - where the portion of the string representing a certain portion of the regex is saved for further analysis. With captures things get more complex - a state node passed in an early match may not be able to commit to a capture, as whether the capture is correct or not depends on later nodes.

Although a turing machine can obviously handle such expressions by treating the regex as a NDFA, and maintaining a stack of non-deterministic state transitions (ie backtracking), it's desirable to avoid the unbounded additional memory/CPU usage and allocations this entails.

So: Is it possible to compile a regular expression with a bounded number of captures $(< k)$ into a DFA, allowing $O(1)$ additional processing at each node, and $O(k)$ additional storage? If not, is there a proof to this effect?

Improve this question
$\endgroup$
3
  • $\begingroup$ what's a 'capture' ? $\endgroup$
    – Suresh Venkat
    May 30, 2011 at 2:23
  • $\begingroup$ @Suresh, added a bit more explanation to the question $\endgroup$
    – bdonlan
    May 30, 2011 at 2:31
  • $\begingroup$ What does “O(1) additional processing at each node” mean? $\endgroup$
    – Tsuyoshi Ito
    May 30, 2011 at 12:00

5 Answers 5

Reset to default
7
$\begingroup$

I have no direct answer, but some additional remarks regarding on the topicality of my paper from this year's STACS which Raphael mentioned in his answer. (Due to space reasons, I opted for a new answer, instead of a comment.)

As far as I understand the question, the classes of regular expressions with $\leq k$ captures corresponded to the classes RegEx(k) of extended regular expressions with at most $k$ variables in my paper. Among the results in the paper, the ones that are probably most relevant to the question are that, even with one variable (the class RegEx(1)),

1) there is no effective way of converting expressions from RegEx(1) to "proper" regular expressions, even if the problem is restricted to those expressions that describe regular languages,

2) even if one is able to convert these expressions with one variable to proper regular expressions (or any other description mechanism for the class of regular languages), the resulting blowup in size is not bounded by any computable function,

3) given an expression $\alpha\in RegEx(1)$, universality (the question whether $L(\alpha)=\Sigma^*$) is not decidable.

This does not directly answer the question, but imposes some limits on possible conversion procedures. For example, if the universality problem for the class of resulting DFAs with extra storage is decidable, such a conversion procedure cannot exist. (On the other hand, although the automata model that is described in the question appears to be underspecified regarding the storage and storage operations, I am under the impression that this problem should be undecidable for the resulting class of automata.)

Among the few papers that deal with regular expressions with variables/backreferences/captures, I know of only two other works that consider something in the direction of limiting the number of variables: Aho's chapter on string matching in the Handbook of TCS (Vol. A), which contains a sketch of a proof that extended regular expressions with at most $k$ backreferences can be matched in time $O(n^{2k})$, and the paper by Reidenbach and Schmid from CIAA 2010, which gives a polynomial time matching algorithm for a larger class of extended regular expressions.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Your second to last paragraph captures the gut feeling of mine that led me to refer to your paper. If the amount of storage allowed is (uniformly) bounded, you get a contradiction to your results. If not, well, what worth does the model have then? (serious question) But then, maybe the OP is not interested in a uniform approach? $\endgroup$
    – Raphael
    May 30, 2011 at 12:37
6
$\begingroup$

You may find Ville Laurikari's masther thesis interesting: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.23.6717 .

He uses "tagged automata" to identify the address where the "capture" is found. From the abstract:

The resulting algorithm makes a single pass over the input string, always using time linearly proportional to the input. Space consumption depends only on the used regular expression, and not on the input string.

There is also an implementation (named TRE) at: http://laurikari.net/tre.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ For anyone else that looks up this paper and associated library I can save your time by mentioning that he seem to NOT be using (the superior) DFA but rather an extension of NFA that he chooses to call TNFA. It is therefore irrelevant to OPs question (AFAICT) as DFA was a requirement (and RE2 already supports capture for NFA matching). $\endgroup$
    – Hannes Landeholm
    Nov 1, 2012 at 13:40
  • 1
    $\begingroup$ Anyone else interested might discover, instead, laurikari's report at laurikari.net/ville/spire2000-tnfa.ps where the conversion of TNFA to Deterministic Automata is discussed. @Hannes, please check before commenting. $\endgroup$
    – Remo.D
    Nov 3, 2012 at 18:14
2
$\begingroup$

Maybe related: Extended regular expressions: Succinctness and decidability (Freydenberger, 2011)

In this paper, it is shown that for every Turing machine, there is an extended regular expression (where extended means with captures if I understand you right) for the language of non-accepting computations.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for the mention! I, too, am not sure how relevant my paper is to this question. My comments to your answer became too large for this comment box; so I decided to set them free as a new answer. $\endgroup$
    – Dominik D. Freydenberger
    May 30, 2011 at 9:18
0
$\begingroup$

I have been trying to find approaches to locate sub-matches within an expression in O(n) (n being the length of the input) time myself.

I have a thought, which I would like to present here, and maybe I could get some help ironing it out.

Consider a regular expression: x(ab|(abc))y

In this case, we are interested in 2 submatch captures. The NFA and DFA for the RE above are:

NFA for x(ab|(abc))y

and

DFA for x(ab|(abc))y

respectively.

We shall focus on the 2nd submatch capture for now, since it poses a greater problem than the first one. The reason that sub-match captures are problematic is because the generated DFA can share a prefix with another expression that is not part of the submatch capture. However, I believe that a DFA that is part of a submatch capture can not share a suffix with another DFA that is not part of the submatch capture that it is part of. (Except for examples such as (ab|(ab)), in which case it doesn't matter).

Keeping this in mind, it seems that it is sufficient to start tracking a capture when we reach a state in the DFA that is composed of a state in the original NFA but corresponds to an open parenthesis to start the submatch capture. For example, state 2 in the DFA is such a state. However, we shall tag exit edges instead of exit nodes since we want to avoid the ambiguity problem. We always tag those edges as interesting edges if the destination DFA state is composed of an NFA state that included a closing parenthesis.

For example, if we tag state 16 in the NFA as an interesting state, then we find that epsilon-closure(16) = (16, 8, 9), and that would correspond to state 6 in the DFA. However, we need to track those edges that are incident on node 6 in the DFA and also have a starting node that originates from some state within the parenthesized expression. Depending on how we generate the NFA from the RE, we can ensure that we never have to deal with this situation.

I believe that if we skip the DFA minimization step then the choice of such a starting node (and hence an edge) is easy to make. For example, consider the following RE: x(ab|(abc)|s)y

The NFA and DFA follow:

NFA for x(ab|(abc)|s)y DFA for x(ab|(abc)|s)y

It would have been entirely possible for an edge to go from state 2 in the DFA to state 7 in the DFA on an input of 's', but because of our construction, this doesn't happen.

The good news seems to be that we can match subexpressions in linear time. However, the bad news seems to be that the number of states in our DFA will at least be exponential in the number of parenthesized subexpressions (since we prefer to branch and replicate everything after it).

Improve this answer
$\endgroup$
-1
$\begingroup$

Implementation of backreferences in regular expressions is equivalent to 3SAT, and therefore NP-complete.

However, simple submatch extraction is possible using only a DFA, even though the majority of implementations do not.

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ The proof for NP-completeness requires that the number of backreferences/captures is not bounded, while this question refers to a bounded number of captures. $\endgroup$
    – Dominik D. Freydenberger
    May 30, 2011 at 9:20
  • $\begingroup$ @Dominik: I am not completely sure what “additional processing at each node” in the question means, but it seems to me that this answer answers the question to some extent. Note that despite the title of the question, the number k of backreferences is not bounded by a constant in the question (if it is bounded by a constant, the phrase “O(k) additional storage” in the question is meaningless). $\endgroup$
    – Tsuyoshi Ito
    May 30, 2011 at 12:03
  • 2
    $\begingroup$ @Tsuyoshi: If captures are backreferences, the last paragraph of the question mentions a bound. On the other hand, after rereading, I am quite sure that the asker does not refer to captures in the context of backreferences, but only in the sense of positions with expressions without backreferences (which makes my answer, Raphael's answer, and the first half of this answer offtopic). $\endgroup$
    – Dominik D. Freydenberger
    May 30, 2011 at 13:38
  • $\begingroup$ @Dominik: I agree with you that captures in the question may not refer to captures for backreferences inside the same regex. On the other hand, I do not think that you understood my previous comment. If the running time has to be O(k) where k is the number of captures for backreferences inside the same regex, it would imply P=NP by the reduction of the first reference in Joe’s answer. $\endgroup$
    – Tsuyoshi Ito
    May 30, 2011 at 13:57
  • $\begingroup$ @Tsuyoshi: You only obtain P=NP if the conversion procedure runs in P-time, which is a different question. Nonetheless, this question is moot: As soon as you consider a regex model with backreferences, my results show that no such conversion procedure exists. $\endgroup$
    – Dominik D. Freydenberger
    May 30, 2011 at 14:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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