Path: csiph.com!weretis.net!feeder6.news.weretis.net!feeder.usenetexpress.com!feeder-in1.iad1.usenetexpress.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end
From: Ben Hanson <jamin.hanson@googlemail.com>
Newsgroups: comp.compilers
Subject: Re: re2c-1.0 released!
Date: Sun, 3 Sep 2017 03:13:11 -0700 (PDT)
Organization: Compilers Central
Lines: 8
Sender: news@iecc.com
Approved: comp.compilers@iecc.com
Message-ID: <17-09-006@comp.compilers>
References: <17-08-007@comp.compilers> <17-09-004@comp.compilers>
Mime-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="40066"; mail-complaints-to="abuse@iecc.com"
Keywords: lex
Posted-Date: 03 Sep 2017 12:02:20 EDT
X-submission-address: compilers@iecc.com
X-moderator-address: compilers-request@iecc.com
X-FAQ-and-archives: http://compilers.iecc.com
Xref: csiph.com comp.compilers:1911

> >As it turns out, submatch extraction is inherently more complex than
> >recognition: it can be solved on NFA, but not on (ordinary) DFA.
>
> I don't know what this means ... every NFA has an equivalent DFA, so
> if a problem can be solved with NFA, it can be solved with DFA.

This is true for regular expressions, but not for capturing regular expressions (irregular expressions?) This is why NFA is traditionally used for regex with captures.