-1
$\begingroup$

Consider the language $L = \{w, w \in \{a,b,c\}^*, n_c(w) = n_a(w) + n_b(w)\}$, where $n_q(\omega)$ is defined to be "the number of $p \in \omega$.

I have tried a couple of PDA's that follow this whole idea of a stack-replacement kind of algorithm, but the reasoning behind it is incorrect. I know it is not the right structure; furthermore, those examples of my previous attempts don't really fit in the context of the question that I'm asking.

There I have a gut feeling that I need to exploit the fact that $0=n_a(w)+n_b(w)-n_c(w)$ but I have absolutely the faintest idea how to do so. When building this kind of "counting machine," what are some design patterns that I can exploit?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

You don't need the "N" in your "NPDA", you can do this with a deterministic counter machine. Every time you see an $a$ or a $b$ increment the counter by $1$, every time you see a $c$ decrement the counter by $1$. When you get to the end of the string, if the counter is at $0$ then accept, else reject.

This is very easy to convert to a standard PDA instead of a counter. As a hint, you will need only one symbol for you stack, and will have to use your finite state to remember if your counter is positive or negative (while the stack remembers the actual magnitude of the count), and you will accept by empty stack.

I am not going to write down the answer more explicitly than this since it is a homework excercise, and you will not learn anything from just copying my answer.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Here's the link to my answer: i.sstatic.net/9dgRg.png Thank you so much for all your help. $\endgroup$
    – alvonellos
    Commented Mar 11, 2014 at 2:54

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.