# Give a push down Automata for this language: the length of is odd and it's middle symbol is 0

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):

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

-

## 1 Answer

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.)

-
What goes down must come up, so to speak. – Brian M. Scott Oct 19 '13 at 20:19
Is this correct? s22.postimg.org/ipf9p6hhd/Untitled.png 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\$.) – inactive... for now Oct 19 '13 at 20:45
Thank you so much, Here is the latest edition:s18.postimg.org/9mj16e16h/Untitled.png – Node.JS Oct 19 '13 at 20:51
@Hooman: The last version looks good to me! – inactive... for now Oct 19 '13 at 20:53