0
$\begingroup$

So I already posted this in Computer Science Stack Exchange but haven't received any real answers and my exam is tomorrow, so I'll post it here too hoping for some clarification:

I'm having problem understanding the first part of this proof. I don't understand why it needs to hang at $(p,\epsilon,\epsilon)$ why can't the automaton just keep going, just reading the rest of the characters without touching the stack? For example what if I have a DPDA that always keeps its stack empty? like, it only reads characters, but doesn't alter the stack. taking $(q_0,a,\epsilon)$ and returning $(q_0,\epsilon)$ every time. Is it because it necessarily needs to do something when given $\epsilon$ as input? In that case can't I just say that if I read $\epsilon$ I return the empty set? Here's the definition I was given of DPDA.
Here's the definition given in Sipser's book
I don't see from these definitions why I shouldn't be able to define a DPDA that has a single state $q_0$ and just reads the whole input without ever touching the stack, like this: $\delta(q_0,a,\epsilon)=(q_0,\epsilon)$ $\forall a\in\Sigma$

$\endgroup$
1
  • 1
    $\begingroup$ Please do not use pictures for critical portions of your post. Pictures may not be legible, cannot be searched and are not view-able to some, such as those who use screen readers. $\endgroup$ Commented May 21, 2024 at 19:08

1 Answer 1

0
$\begingroup$

The problem was that a word will only be accepted by empty stack if it empties the stack just as I finish reading the word. That's why in the proof above we can't accept ww'. But the automata that I described are entirely possible going by the definitions.
It's perfectly legal to not read anything from the stack, in that case the automaton would act as an FDA.
So to sum it up, the automaton is allowed to keep going, not touching the stack, but then that word wouldn't be accepted by empty stack.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.