# 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: [$$$/extract_tex]] $$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 • What have you tried? Where did you get stuck? We do not want to just hand you the solution; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for tips on asking questions about exercise problems. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? – Raphael Nov 13 '18 at 14:59 ## 2 Answers 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: 1. $$q_1 \to q_2$$, stack: $$[$$$
2. $$q_2 \to q_2$$, stack: $$[\, 1]$$
3. $$q_2 \to q_3$$, stack: $$[\, 1]$$
4. $$q_3 \to q_3$$, stack: $$[\]$$
5. $$q_3 \to q_4$$, stack: $$[]$$

A PDA is non-deterministic. Nondeterministic automata accept a string w if any path along which w might be processed results in w's being accepted. so the PDA will try all paths and only accept the string if one of these paths landed in an accept state.

For a detailed explanation check these links: