$B = \{w \in \{0,1\}^* | w^R = w, w \text{ length is odd} \}$


enter image description here

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

  • $\begingroup$ 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? $\endgroup$
    – Raphael
    Nov 13, 2018 at 14:59

2 Answers 2


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:


Neso academy- Pushdown Automata Example (Even Palindrome) : https://www.youtube.com/watch?v=xHj2WI1Rrl4&list=PLBlnK6fEyqRgp46KUv4ZY69yXmpwKOIev&index=82&app=desktop


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.