Path: csiph.com!usenet.pasdenom.info!dedibox.gegeweb.org!gegeweb.eu!nntpfeed.proxad.net!proxad.net!feeder1-2.proxad.net!usenet-fr.net!nerim.net!novso.com!newsfeed.xs4all.nl!newsfeed2a.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail Return-Path: X-Original-To: python-list@python.org Delivered-To: python-list@mail.python.org X-Spam-Status: OK 0.051 X-Spam-Evidence: '*H*': 0.90; '*S*': 0.00; 'modify': 0.07; 'transform': 0.07; 'string': 0.09; 'subject:string': 0.09; 'subject:How': 0.10; 'accepting': 0.14; 'subject: \n ': 0.16; 'subject:possible': 0.16; 'wrote:': 0.18; 'library': 0.18; 'machine': 0.22; 'input': 0.22; 'question': 0.24; 'header:In- Reply-To:1': 0.27; 'point': 0.28; 'am,': 0.29; 'characters': 0.30; 'message-id:@mail.gmail.com': 0.30; 'subject:other': 0.31; 'subject:that': 0.31; 'though.': 0.31; 'run': 0.32; 'running': 0.33; 'not.': 0.33; "i'd": 0.34; 'but': 0.35; 'received:google.com': 0.35; '(we': 0.36; 'possible': 0.36; 'should': 0.36; 'to:addr:python-list': 0.38; 'does': 0.39; 'to:addr:python.org': 0.39; 'easy': 0.60; 'entire': 0.61; 'strictly': 0.61; 'such': 0.63; 'skip:n 10': 0.64; 'interest': 0.64; 'more': 0.64; 'determine': 0.67; 'manner': 0.72; 'subject:check': 0.84; 'state.': 0.95 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :content-type:content-transfer-encoding; bh=PLpPwnw+gW4ALbGi/PBFXzqtLycrbjeYOaET6aiVx6Y=; b=r8EsR1sOrcRaV3k82HVQexG8AQqRGzCSEahLKtt+kW1uUCxoiyv+p4E0znDtzb7+IP M6kO0CxIM1W/E/rzUJPJEr1T/1Q//G9pMcTmJQVftfSG7jsP3X5casGbnP6eZR8/9pa2 xzDKZpmS6UWETNuLAYrEgFgVbCW+s3kqu9nL5h9BSWdzlmRxSZYtDeoPTDjkOaT316n1 B5BpaOLqs0RDtANLBtyNOBwpRpQ1XXc6BCIJeqP6whJbID0yPPFPbV/4hnero37p134J 4clH/siq9QQh6tG1DMBBb3Ifa8MV9FKcj2GnMGKq4mXC8HIaa8uzmHmoims7pjlidbWy ofjA== X-Received: by 10.66.119.103 with SMTP id kt7mr5309854pab.95.1412706981527; Tue, 07 Oct 2014 11:36:21 -0700 (PDT) MIME-Version: 1.0 In-Reply-To: References: From: Ian Kelly Date: Tue, 7 Oct 2014 12:35:41 -0600 Subject: Re: How do I check if a string is a prefix of any possible other string that matches a given regex. To: Python Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable X-BeenThere: python-list@python.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: General discussion list for the Python programming language List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Newsgroups: comp.lang.python Message-ID: Lines: 13 NNTP-Posting-Host: 2001:888:2000:d::a6 X-Trace: 1412706991 news.xs4all.nl 2959 [2001:888:2000:d::a6]:43223 X-Complaints-To: abuse@xs4all.nl Xref: csiph.com comp.lang.python:78808 On Tue, Oct 7, 2014 at 10:15 AM, wrote: > Logically, I'd think it should be possible by running the input string ag= ainst the state machine that the given regex describes, and if at some poin= t all the input characters are consumed, it's a match. (We don't have to ru= n 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.