Build a pushdown automata to $L=\{a^n b^m c^k | m = n + k\}$

Question

I have this PDA but I would like the accept too when it is receveid a letter b or c as first string.

For example

bbbbaacc
ccaabbbb ${}{}{}{}{}$
cacabbbb

Answer 1

This can be done as follows:

There are two elements which can be on the stack, $p$ and $q$. The stack begins as empty.

When the automaton reads a $b$, it either removes a $q$, if a $q$ is on the top of the stack, or pushes a $p$ otherwise.

When the automaton reads an $a$ or $c$, it either removes a $p$, if a $p$ is on the top of the stack, or pushes a $q$ otherwise.

The automaton will have an empty stack iff the string it reads satisfies $\#b = \#a + \#c$.

In fact, note that the stack, at any point, has either a positive number of $p$s and no $q$s, a positive number of $q$s and no $p$s, or is empty.

Define the "value" of the stack to be the number of $p$s minus the number of $q$s. The value of the stack is always equal to $\#b - \#a - \#c$, where $\#b$ is the number of $b$s read so far, etc. This is how correctness is proved.