General DPDA Question

Should a DPDA always have a REJECT state? I see a lot of the DPDA examples that I get online don't have REJECT states. If a word is not accepted it's rejected, right?!? (I know its pointless having multiple REJECT states)

i just got my solutions for ass 1, and it had no reject states, along with some kind of explanation. hmm. i was hoping for something like "if it doesn't go to accept then we can assume it goes to a common reject", but nope.

RiaanR Wrote:
-------------------------------------------------------
> Should a DPDA always have a REJECT state? I see a
> lot of the DPDA examples that I get online don't
> have REJECT states. If a word is not accepted it's
> rejected, right?!? (I know its pointless having
> multiple REJECT states)


The number of reject states does not influence
the determinism (or lack thereof) of a PDA. I'm not
too sure how this (mis)information gets propagated(sp?)
in each thread as the textbook does make it clear what
the definitions are, but maybe it's time to address it.

The difference between a deterministic PDA and
and a non-deterministic PDA is this:

In a DPDA, a word that is accepted must always be
accepted no matter how many different paths exist
towards acceptance. The same applies for a word
that is rejected.

In a non-D PDA, a word may be accepted along one
path while *also* being rejected along a different path.

The above implies that a PDA that loops infinitely or
crashes on a certain word can be (but is not necessarily)
deterministic; i.e. the absence of a reject state has no
effect on the determinism of a PDA.

My standard disclaimer applies:

   "I'd be very happy if someone would care to cite the
    text in proving the above wrong; I've been using it now
    for a while and would appreciate any corrections."

--
Learn something new - updated weekly