Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.compilers > #2390
| 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> (permalink) |
| 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 |
Show key headers only | View raw
On 2019-12-20, Andy <borucki.andrzej@gmail.com> 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
Back to comp.compilers | Previous | Next — Previous in thread | Next in thread | Find similar
Reachability of DFA part Andy <borucki.andrzej@gmail.com> - 2019-12-20 04:53 -0800
Re: Reachability of DFA part Kaz Kylheku <493-878-3164@kylheku.com> - 2019-12-20 16:06 +0000
Re: Reachability of DFA part Andy <borucki.andrzej@gmail.com> - 2019-12-21 01:15 -0800
Re: Reachability of DFA part Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2019-12-21 19:58 +0100
csiph-web