[banish-m4]

NFAs are apparently undecidable since the same input can go to multiple states. DFA states can only go to one state when given a particular input sequence.

The Dragon book contains an NFA to DFA algorithm (powerset) which explodes states with multiple exiting token transitions.

PS: All your DAGs are belong to us.

[mikhailfranco]

It is possible to implement NFAs directly, in parallel:

https://github.com/mike-french/myrex

Just fan-out messages to all downstream states. Let a fair runtime system evaluate all progress, then tally results along all paths, for example:

https://github.com/mike-french/myrex?tab=readme-ov-file#exec...

The approach can also be adapted to captures and their many, many possible ambiguities. There is an example that generalizes a highly ambiguous match given in Cox: regex (a?){m}(a*){m} against a string of a{m}. The case m=9 gives 864k possible solutions (traversals), you may optionally ask for all of them to be returned:

https://github.com/mike-french/myrex?tab=readme-ov-file#ambi...

The processes share nothing, all state is in the messages, so a single network can process multiple input strings simultaneously. It can also generate Monte-Carlo strings that match the regex, and those may also proceed simultaneously.

[banish-m4]

That's identical to NFA->DFA conversion but with dynamic programming.

[gliptic]

NFAs are decidable. As you said, a NFA can be converted to a DFA which is decidable. Maybe you mean they are non-deterministic (that's in the name)?

[banish-m4]

You know what I meant. I used the wrong word.

[ablob]

There exist algorithms that deal with state blow-up. In fact, these algorithms project any given DFA into an equivalent DFA of minimal size - guaranteeing a minimal automaton for the language that is accepted by it. In essence, you build equivalence classes between states with respect to possible paths they can take into other equivalence classes for further input. State machines for LR-Grammars are vastly more complex in comparison to NFA automata, so for most (if not all) applications, a computer that can deal with LR-Grammars will be able to handle a NFA conversion with a subsequent minimization.

[samatman]

Decidability is whether one can statically determine if an algorithm halts for a given input. NFAs halt for all inputs, by construction.