I have a PDA A = ({q0, q1}, Σ = {a, b}, Γ = {a}, δ, F = {q1}), with these transition functions δ:






The exercise asks me to explain the structure of the words accepted. I have designed the PDA but i'm having problems understanding what kind of words the PDA accepts. Any kind of help is really appreciated.

  • $\begingroup$ I think it accepts all words with length bigger than $1$. This is probably not what you wanted this PDA to do... $\endgroup$
    – nir shahar
    Commented Oct 31, 2021 at 14:40
  • $\begingroup$ This PDA is given to me by the exercise, i have to design it and explain what kind of words it accepts $\endgroup$
    – rsky
    Commented Oct 31, 2021 at 15:17

1 Answer 1


I suppose that your acceptance mode is by final state and empty stack.

The loops around $q_0$ add one stack symbol for each input letter that is read. After this, the third transition reads an $a$ without touching the stack. Finally, all transitions around $q_1$ remove one stack symbol for each input letter that is read.

To reach an empty stack in $q_1$, the number of loops around it has to be the same as around $q_0$. Exactly in the middle there is one $a$ that takes you from $q_0$ to $q_1$. Thus the language would be $$\{w_1\cdot a \cdot w_2: |w_1| = |w_2|\}.$$


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.