Re: Reachability of DFA part

From	Kaz Kylheku <493-878-3164@kylheku.com>
Newsgroups	comp.compilers
Subject	Re: Reachability of DFA part
Date	2019-12-20 16:06 +0000
Organization	Aioe.org NNTP Server
Message-ID	<19-12-009@comp.compilers> (permalink)
References	<19-12-008@comp.compilers>

Show all headers | 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

Thread

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