Take the 2-minute tour ×
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.

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|improve this question

1 Answer 1

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|improve this answer
1  
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 –  Hooman Oct 19 '13 at 20:37
1  
@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$.) –  Arthur Fischer Oct 19 '13 at 20:45
    
Thank you so much, Here is the latest edition:s18.postimg.org/9mj16e16h/Untitled.png –  Hooman Oct 19 '13 at 20:51
1  
@Hooman: The last version looks good to me! –  Arthur Fischer Oct 19 '13 at 20:53

Your Answer

 
discard

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.