Why is this pushdown automaton for some palindromes right? $B = \{w \in \{0,1\}^* | w^R = w, w \text{ length is odd} \}$

Solution:



For example: $111$ should be accepted

steps are

$q_1 \to q_2$ stack: [$\$$]

$q_2 \to q_2$ stack: $[\$, 1, 1]$ (using up $11$ only having a single $1$ left)

$q_2 \to q_3$ stack: $[\$, 1, 1]$ (no change except we lost our final $1$)

$q_3 \to$ (no strings left to use)

I'm confused understanding this
PDAs are nondeterministic. Although you have found a valid computation which does not lead to an accept state, a PDA is said to accept its input if there is some valid computation which does lead to an accept state.

In this case (input $111$), an accepting computation is:


$q_1 \to q_2$, stack: $[\$]$
$q_2 \to q_2$, stack: $[\$, 1]$
$q_2 \to q_3$, stack: $[\$, 1]$
$q_3 \to q_3$, stack: $[\$]$
$q_3 \to q_4$, stack: $[]$