Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #78805 > unrolled thread

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

Back to article view | Back to comp.lang.python

Contents

  How do I check if a string is a prefix of any possible other string that matches a given regex. jonathan.slenders@gmail.com - 2014-10-07 09:15 -0700
    Re: How do I check if a string is a prefix of any possible other string that matches a given regex. Joshua Landau <joshua@landau.ws> - 2014-10-07 18:01 +0100
    Re: How do I check if a string is a prefix of any possible other string that matches a given regex. Ian Kelly <ian.g.kelly@gmail.com> - 2014-10-07 12:35 -0600
      Re: How do I check if a string is a prefix of any possible other string that matches a given regex. jonathan.slenders@gmail.com - 2014-10-07 14:48 -0700
        Re: How do I check if a string is a prefix of any possible other string that matches a given regex. MRAB <python@mrabarnett.plus.com> - 2014-10-08 00:39 +0100
          Re: How do I check if a string is a prefix of any possible other string that matches a given regex. jonathan.slenders@gmail.com - 2014-10-08 01:48 -0700
        Re: How do I check if a string is a prefix of any possible other   string that matches a given regex. Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2014-10-09 10:24 +1300

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

Hi everyone,


Probably I'm turning the use of regular expressions upside down with this question. I don't want to write a regex that matches prefixes of other strings, I know how to do that. I want to generate a regex -- given another regex --, that matches all possible strings that are a prefix of a string that matches the given regex.


E.g. You have the regex  ^[a-z]*4R$  then the strings "a", "ab", "A4" "ab4" are prefixes of this regex (because there is a way of adding characters that causes the regex to match), but "4a" or "a44" or not.
How do I programmatically create a regex that matches "a", "ab", "A4", etc.. but not "4a", "a44", etc..

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...

Thanks a lot, if anyone knows the answer to this question!


Cheers,
Jonathan

[toc] | [next] | [standalone]

#78806

On 7 October 2014 17:15,  <jonathan.slenders@gmail.com> wrote:
> Probably I'm turning the use of regular expressions upside down with this question. I don't want to write a regex that matches prefixes of other strings, I know how to do that. I want to generate a regex -- given another regex --, that matches all possible strings that are a prefix of a string that matches the given regex.
> [...]
> 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...

How wide a net are you counting "regular expressions" to be? What
grammar are you using?

[toc] | [prev] | [next] | [standalone]

#78808

On Tue, Oct 7, 2014 at 10:15 AM,  <jonathan.slenders@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.

[toc] | [prev] | [next] | [standalone]

#78813

> > 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.

[toc] | [prev] | [next] | [standalone]

#78816

On 2014-10-07 22:48, jonathan.slenders@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

[toc] | [prev] | [next] | [standalone]

#78830

Le mercredi 8 octobre 2014 01:40:11 UTC+2, MRAB a écrit :
> 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

Wow, thanks a lot! That really helps me.

[toc] | [prev] | [next] | [standalone]

#78852 — Re: How do I check if a string is a prefix of any possible other string that matches a given regex.

jonathan.slenders@gmail.com wrote:

>>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.

Not *every* state -- that will give you an FSM that
accepts any string!

-- 
Greg

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web