Let $L = \{ww^r\ |\ w \in \{a, b\} \}, r \in \mathbb{N}$. Prove that $L$ can't be defined by a deterministic pushdown automaton.
I described the transition function of the automaton:
$M = ({q_0, q_1, q_2}, \{a, b, Z\}, \delta, \sigma, q_0, Z0, q_1)$
$\delta(q_0, a, Z) = \{q_0, aZ\}$
$\delta(q_0, b, Z) = \{q_0, bZ\}$
$\delta(q_0, a, a) = (\{q_0, aa\}, \{q_1, e\})$
$\delta(q_0, b, b) = (\{q_0, bb\}, \{q_1, e\})$
$\delta(q_0, a, b) = \{q_0, ab\}$
$\delta(q_0, b, a) = \{q_0, ba\}$
$\delta(q_0, a, a) = \{q_1, e\}$
$\delta(q_0, b, b) = \{q_1, e\}$
$\delta(q_0, e, e) = \{q_2, e\}$
My lecturer proved this as follows:
Prove by contradiction. Let word detected by some automaton $M$ (with bounded depth stack). Then exist some long word $w$ with recurring stack state – $p$. $w = w_1xw_2yw_3tw_4kw_5zw_6nw_7mw_8lw_9dw_{10}c$, where $x, y, t, k, z, n, m, l, d, c \in \Sigma$;
$xw_2y$, $tw_4k$, etc... have stack state called p. Upgrade the word $w$ as follows:
let start subword from $k$ (symbol from $\Sigma)$ and finish on the same letter so that the word $kwk$ has stack $p$. This a word exists by the rules of combinatorics (actually, I don't understand what the lecturer meant). Let this word is $xw_2y$, write it to the end of the $w$ and get an unsymmetrical word that does not satisfy the grammar, but is recognized by the DPDA.
I absolutely don't understand what the lecturer wanted to show with this proof. I will be glad to any help.
Your PDA is not determininstic, since in lines 3 and 4 it has options forwhat to do. Further, it does definitely not accept the desired language.
The obvious approach is to put $w$ on the stack and then compare it letter by letter to $w^r$. However, one would have to know when the middle is reached. A non-deterministic PDA can just guess this, but for a deterministic one there is no way of knowing. A marked palindrome language like $\{wcw^r : w\in \{a,b\}\}$ could be accepted by a det PDA.
From what you write, the proof is not really clear. Especially why you can suppose that the depth of the stack is bounded. If you can, then of course some stack state has to be repeated for a sufficiently long word, and then you can make this word longer like in the pumping lemma, probably destrpying the palindrome structure.