Re: Pure Regular Expression Engines and Literal Clusters

> On 13 Oct 2019, at 15:00, Richard Wordingham via Unicode <unicode_at_unicode.org> wrote:
>
>>> On Sat, 12 Oct 2019 21:36:45 +0200
>>> Hans Åberg via Unicode <unicode_at_unicode.org> wrote:
>>>
>>>>> On 12 Oct 2019, at 14:17, Richard Wordingham via Unicode
>>>>> <unicode_at_unicode.org> wrote:
>>>>>
>>>>> But remember that 'having longer first' is meaningless for a
>>>>> non-deterministic finite automaton that does a single pass through
>>>>> the string to be searched.
>>>>
>>>> It is possible to identify all submatches deterministically in
>>>> linear time without backtracking — I a made an algorithm for
>>>> that.
>
> I'm now beginning to wonder what you are claiming.

I start with a NFA with no empty transitions and apply the subset DFA construction dynamically for a given string along with some reverse NFA-data that is enough to transverse backwards when a final state arrives. The result is a NFA where all transverses is a match of the string at that position.
Received on Sun Oct 13 2019 - 08:29:31 CDT