Design a Pushdown Automata, accepting either by final state or by empty stack to accept the set of all strings of 0’s and 1’s such that no prefix has more 1’s than 0’s

This is a homework question, but not graded.

I'm not looking for the answer, right now I'm just trying to understand the question. I don't understand what sort of words would be accepted and what would be rejected. For example, I can't understand whether the following word would be accepted:

  • 011011 ; where 01 is prefix and 1011 is suffix
  • 011011 ; where 011 is prefix and 011 is suffix
  • 011011 ; where 0110 is prefix and 11 is suffix

My question is: Given a word, how do I know which part of it is the prefix?

Please try to give an explanation without the actual PDA answer, I'd like to try it myself first.


1 Answer 1


If we have a word, $w=a_1a_2\dots a_n$ where the $a_i$ are characters from the underlying alphabet, then the prefixes of $w$ are the empty word, $\epsilon$, and the words $a_1$, $a_1a_2$, $a_1a_2a_3$, ..., $a_1a_2\dots a_{n-1}a_n$. In informal terms, the prefixes of a word consist of all left-hand segments of the word.


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.