Can 2 items be added/taken away from a stack in push down automata at once?

916 Views Asked by At

Here is a language and 2 ways (I hope) of representing it with a PDA.

examples

Can I use the notation (b,a $\to$ ee) or anything of the like, to take away 2 items from the top of a list at once? Such as I have used in example A. Or do I need to work around this by using a PDA like in example B?

Generally checking my work is also appreciated

1

There are 1 best solutions below

0
On

In general, no. The shorthand $(a,b \to xyz)$ is often used, but means something else than what you're trying to do here. Recall that by $(a,b \to c)$ we mean that $a$ is the symbol that is read, $b$ is the symbol on top of the stack that is replaced with $c$. $(a,b \to xyz)$ is then usually taken to mean that $(a,b \to x) \to (\varepsilon,\varepsilon \to y) \to (\varepsilon,\varepsilon \to z)$, in which case $(a,b \to \varepsilon \varepsilon)$ would be the same as $(a,b \to \varepsilon)$.

As far as I can see, your solution B is also not correct, since you never check that there are twice as many b's as there are a's. Here is my attempt at an answer. enter image description here

Notice that the start state is also an accept state since $m \geq 0$.