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


Groups > comp.lang.python > #78813

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

Newsgroups comp.lang.python
Date 2014-10-07 14:48 -0700
References <dbf06cce-19ae-4859-9cc1-97f70d1bacfb@googlegroups.com> <mailman.14664.1412706991.18130.python-list@python.org>
Message-ID <8c47cee0-7fec-4fb7-b32a-ddac6fd7c247@googlegroups.com> (permalink)
Subject Re: How do I check if a string is a prefix of any possible other string that matches a given regex.
From jonathan.slenders@gmail.com

Show all headers | View raw


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

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread


Thread

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

csiph-web