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

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

<blockquote>
  <p>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.</p>
</blockquote>

<p>There is also an implementation (named TRE) at: <a href="http://laurikari.net/tre">http://laurikari.net/tre</a>.</p>

CC BY-SA 3.0
2012-11-01T13:40:46.650Z
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).
Hannes Landeholm
CC BY-SA 3.0
2012-11-03T18:14:47.287Z
Anyone else interested might discover, instead, laurikari's report at http://laurikari.net/ville/spire2000-tnfa.ps where the conversion of TNFA to Deterministic Automata is discussed.  @Hannes, please check before commenting.
Remo.D
CC BY-SA 3.0
2011-05-30T11:53:57.710Z
2011-05-30T11:53:57.710Z
Remo.D
<p>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.)</p>

<p>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)),</p>

<p>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,</p>

<p>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,</p>

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

<p>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.)</p>

<p>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 <a href="https://dspace.lboro.ac.uk/dspace-jspui/handle/2134/7957" rel="noreferrer">paper</a> by Reidenbach and Schmid from CIAA 2010, which gives a polynomial time matching algorithm for a larger class of extended regular expressions. </p>

CC BY-SA 3.0
2011-05-30T12:37:01.653Z
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?
Raphael
CC BY-SA 3.0
2011-05-30T09:18:15.477Z
2011-05-30T09:18:15.477Z
Dominik D. Freydenberger
<p>Maybe related: <a href="http://www.tks.informatik.uni-frankfurt.de/getpdf?id=686" rel="nofollow">Extended regular expressions: Succinctness and decidability</a> (Freydenberger, 2011)</p>

<p>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.</p>

CC BY-SA 3.0
2011-05-30T09:18:34.087Z
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.
Dominik D. Freydenberger
CC BY-SA 3.0
2011-05-30T05:59:46.877Z
2011-05-30T05:59:46.877Z
Raphael
<p>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.</p>

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

<p>Consider a regular expression: x(ab|(abc))y</p>

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

<p><img src="https://i.sstatic.net/EhK3T.png" alt="NFA for x(ab|(abc))y"></p>

<p>and</p>

<p><img src="https://i.sstatic.net/BxRrq.png" alt="DFA for x(ab|(abc))y"></p>

<p>respectively.</p>

<p>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).</p>

<p>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.</p>

<p>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.</p>

<p>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</p>

<p>The NFA and DFA follow:</p>

<p><img src="https://i.sstatic.net/JfpNz.png" alt="NFA for x(ab|(abc)|s)y">
<img src="https://i.sstatic.net/bUGkw.png" alt="DFA for x(ab|(abc)|s)y"></p>

<p>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.</p>

<p>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).</p>

CC BY-SA 3.0
2013-11-01T05:37:05.200Z
2013-11-01T05:37:05.200Z
dhruvbird
<p>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. <a href="http://re2c.org/" rel="nofollow">re2c</a>.</p>

<p>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. </p>

<p>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.</p>

<p>So: Is it possible to compile a regular expression with a bounded number of captures $(&lt; 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?</p>

CC BY-SA 3.0
2011-05-30T02:23:34.707Z
what's a 'capture' ?
Suresh Venkat
CC BY-SA 3.0
2011-05-30T02:31:10.023Z
@Suresh, added a bit more explanation to the question
bdonlan
CC BY-SA 3.0
2011-05-30T12:00:11.467Z
What does “O(1) additional processing at each node” mean?
Tsuyoshi Ito
<fl.formal-languages><regular-expressions><dfa>
Is it possible to represent a regular expression with bounded captures using a DFA and O(1) additional processing?
bdonlan
# Is it possible to represent a regular expression with bounded captures using a DFA and O(1) additional processing?

(Asked by: username_0 on 2011-05-30)

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](http://re2c.org/).

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?

**Tags:** fl.formal-languages, regular-expressions, dfa
> **Comments:**
> **username_1**: what's a 'capture' ?  
> **username_0**: @Suresh, added a bit more explanation to the question  
> **username_2**: What does “O(1) additional processing at each node” mean?  

---

## 4 answers

### Answer by username_5 on 2011-05-30. Score: 7

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](https://dspace.lboro.ac.uk/dspace-jspui/handle/2134/7957) by Reidenbach and Schmid from CIAA 2010, which gives a polynomial time matching algorithm for a larger class of extended regular expressions.

> **Comments:**
> **username_6**: 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?  

---

### Answer by username_3 on 2011-05-30. Score: 6

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>.

> **Comments:**
> **username_4**: 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).  
> **username_3**: Anyone else interested might discover, instead, laurikari's report at http://laurikari.net/ville/spire2000-tnfa.ps where the conversion of TNFA to Deterministic Automata is discussed.  @Hannes, please check before commenting.  

---

### Answer by username_6 on 2011-05-30. Score: 2

Maybe related: [Extended regular expressions: Succinctness and decidability](http://www.tks.informatik.uni-frankfurt.de/getpdf?id=686) (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.

> **Comments:**
> **username_5**: 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.  

---

### Answer by username_7 on 2013-11-01. Score: 0

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](https://i.sstatic.net/EhK3T.png)

and

![DFA for x(ab|(abc))y](https://i.sstatic.net/BxRrq.png)

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](https://i.sstatic.net/JfpNz.png)
![DFA for x(ab|(abc)|s)y](https://i.sstatic.net/bUGkw.png)

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).


---

