Path: csiph.com!3.us.feeder.erje.net!feeder.erje.net!news.alt.net!feeder.usenetexpress.com!tr3.iad1.usenetexpress.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end From: Kaz Kylheku <493-878-3164@kylheku.com> Newsgroups: comp.compilers Subject: Re: Reachability of DFA part Date: Fri, 20 Dec 2019 16:06:44 +0000 (UTC) Organization: Aioe.org NNTP Server Lines: 27 Sender: news@iecc.com Approved: comp.compilers@iecc.com Message-ID: <19-12-009@comp.compilers> References: <19-12-008@comp.compilers> Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="60976"; mail-complaints-to="abuse@iecc.com" Keywords: DFA Posted-Date: 20 Dec 2019 11:41:01 EST X-submission-address: compilers@iecc.com X-moderator-address: compilers-request@iecc.com X-FAQ-and-archives: http://compilers.iecc.com Xref: csiph.com comp.compilers:2390 On 2019-12-20, Andy wrote: > Sometmimes part of DFA can be unreached: ab(a|b)*ba - ba is unreachable. That doesn't appear to be so; of course, the regular expression demands a match on the trailing "ba". In the NFA automaton, every time the prefix of the input given so far ends in ba, the machine will be in an acceptance state corresponding to that trailing ba. Possible NFA graph: .b -. .- b -> (3) -> a -> ((4)) | | v , (0) -> a (1) -> b (2) --. ^ | | | ` a -' In the DFA, there will be a reachable state (subset of NFA states) which contains ((4)). -- TXR Programming Lanuage: http://nongnu.org/txr Music DIY Mailing List: http://www.kylheku.com/diy ADA MP-1 Mailing List: http://www.kylheku.com/mp1