How do I check if a string is a prefix of any possible other string that matches a given regex.

[Ian Kelly]

On Tue, Oct 7, 2014 at 10:15 AM,  <jonathan.slenders at gmail.com> wrote:
> Logically, I'd think it should be possible by running the input string against the state machine that the given regex describes, and if at some point all the input characters are consumed, it's a match. (We don't have to run the regex until the end.) But I cannot find any library that does it...

Strictly speaking, a DFA or NFA always consumes the entire input; the
question of interest is whether it halts in an accepting state or not.

It would be easy to transform a DFA or NFA in the manner that you
want, though.  For each non-accepting state, determine whether it has
any transitions that lead in one or more steps to an accepting state.
Modify the FSM so that each such state is also an accepting state.