5
$\begingroup$

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,

$\endgroup$
0

1 Answer 1

Reset to default
4
$\begingroup$

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

$\endgroup$
6
  • 2
    $\begingroup$ What goes down must come up, so to speak. $\endgroup$
    – Brian M. Scott
    Oct 19, 2013 at 20:19
  • $\begingroup$ Is this correct? s22.postimg.org/ipf9p6hhd/Untitled.png instead of 1 in the middle it should be 0 $\endgroup$
    – Node.JS
    Oct 19, 2013 at 20:37
  • 1
    $\begingroup$ @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$.) $\endgroup$
    – user642796
    Oct 19, 2013 at 20:45
  • $\begingroup$ Thank you so much, Here is the latest edition:s18.postimg.org/9mj16e16h/Untitled.png $\endgroup$
    – Node.JS
    Oct 19, 2013 at 20:51
  • 1
    $\begingroup$ @Hooman: The last version looks good to me! $\endgroup$
    – user642796
    Oct 19, 2013 at 20:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .