4 ms·

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

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.

gliptic 2y ago
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 2y ago
  You know what I meant. I used the wrong word.
ablob 2y ago
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.
mikhailfranco 2y ago
It is possible to implement NFAs directly, in parallel: https://github.com/mike-french/myrex 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#executor-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#ambiguous-example 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 2y ago
  That's identical to NFA->DFA conversion but with dynamic programming.
samatman 2y ago
Decidability is whether one can statically determine if an algorithm halts for a given input. NFAs halt for all inputs, by construction.

gliptic 2y ago

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 2y ago
You know what I meant. I used the wrong word.

ablob 2y ago

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.

mikhailfranco 2y ago

It is possible to implement NFAs directly, in parallel: https://github.com/mike-french/myrex 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#executor-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#ambiguous-example 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 2y ago
That's identical to NFA->DFA conversion but with dynamic programming.

samatman 2y ago

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