Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Give a push down automaton for this language:

{w| the length of w is odd and it's middle symbol is 0}

Here is the CFG I wrote for this language:

S --> 0|0S0|0s1|1s0|1s1

This what I have done for odd length part (I'm not using a stack for first part but I'm sure I need to use stack for second part):

enter image description here

I've spent days on this question but no luck,

share|cite|improve this question
up vote 3 down vote accepted

Broad Hint: You shouldn't have to check that the string has odd length. Note that a string $w$ is in the language $L$ described above iff there is an occurrence of the symbol $\mathtt{0}$ in $w$ such that there are exactly as many symbols in $w$ appearing before that occurrence of $\mathtt{0}$ as there are after. (For a hint that is a bit more direct, whenever you read a $\mathtt{0}$ from the string non-deterministically guess that this is the correct one, using the stack to check whether the above property holds.)

share|cite|improve this answer
What goes down must come up, so to speak. – Brian M. Scott Oct 19 '13 at 20:19
Is this correct? instead of 1 in the middle it should be 0 – Node.JS Oct 19 '13 at 20:37
@Hooman: Not quite. The PDA described in the image accepts all odd-length palindromes with a $\mathtt{1}$ in the middle (or a $\mathtt{0}$ in the middle if you switch that middle $\mathtt{1}$ to a $\mathtt{0}$). But it can be modified to give you a solution. In particular, when you are pushing symbols onto the stack, you are only interested in the number of symbols you have read, not the type of symbols. (Also, the last transition should be $\varepsilon, \mathtt{\$} \rightarrow \varepsilon$.) – arjafi Oct 19 '13 at 20:45
Thank you so much, Here is the latest – Node.JS Oct 19 '13 at 20:51
@Hooman: The last version looks good to me! – arjafi Oct 19 '13 at 20:53

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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