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

[MRAB]

On 2014-10-07 22:48, 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.
>
> Thanks, I'll make every state of the FSM an accepting state.
>
> My use case is to implement autocompletion for a regular language.
> So I think if the input is accepted by the FSM that I build, it's a
> valid "prefix", and the autocompletion can be generated by looking
> at which transitions are possible at that point.
>
> More pointers are welcome, but I think that I have enough to start
> the implementation.
>
If you're not interested in generating an actual regex, but only in
matching the prefix, then it sounds like you want "partial matching".

The regex module supports that:

https://pypi.python.org/pypi/regex