Return to the
comp.compilers page.
Search the
comp.compilers archives again.
| Related articles |
|---|
| Reachability of DFA part borucki.andrzej@gmail.com (Andy) (2019-12-20) |
| Re: Reachability of DFA part 493-878-3164@kylheku.com (Kaz Kylheku) (2019-12-20) |
| Re: Reachability of DFA part borucki.andrzej@gmail.com (Andy) (2019-12-21) |
| Re: Reachability of DFA part DrDiettrich1@netscape.net (Hans-Peter Diettrich) (2019-12-21) |
| Reachability of DFA part christopher.f.clark@compiler-resources.com (Christopher F Clark) (2019-12-23) |
| Re: Reachability of DFA part 493-878-3164@kylheku.com (Kaz Kylheku) (2019-12-24) |
| From: | Kaz Kylheku <493-878-3164@kylheku.com> |
| Newsgroups: | comp.compilers |
| Date: | Fri, 20 Dec 2019 16:06:44 +0000 (UTC) |
| Organization: | Aioe.org NNTP Server |
| References: | 19-12-008 |
| 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 |
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
Return to the
comp.compilers page.
Search the
comp.compilers archives again.