If we had a language $$\sum = \{a,b,c\}$$ for a pushdown automata, and the transition $$a;A/AA$$ means "If you read in an a and A is at the top of the stack, push A", then would you be able to push nothing if you encounter an a and A is at the top of the stack with the transition: $$a;A/\epsilon \space C$$
I am new to this notation so I am unsure of if I am doing it correctly.


1 Answer 1


In a commonly used model for pushdown atomata instructions of the automaton are of the form $(p,a,A,q,\alpha)$ meaning in state $p$, read $a$ from the input, pop $A$ from the stack, change to state $q$ and push $\alpha$ to the stack. In a diagram for the pda this can be represented as an edge from $p$ to $q$ labelled by $a; A/\alpha$. Note the first symbol of $\alpha$ end at the top of the stack.

There are some complications. First $a$ can be the empty string, so that the automaton ignores the letter on its input tape. To the contrary, the automaton cannot easily ignore its stack. The topmost symbol is always popped.

So if we want to perform the instruction "read $a$ whatever is on the stack" this is implemented as a set of instructions $(p,a,A,q,A)$ for all stack symbols $A$. If we want to perform "read $a$ when $A$ is on the stack (and leave $A$ there)" we just have the instruction $(p,a,A,q,A)$ for this particular symbol $A$. This seems to be your case.

Also the instruction "read $a$ and pop $A$" is then $(p,a,A,q,\varepsilon)$, pushing nothing after popping $A$.

Finally, the fact that we always need to pop at least one symbol means that formally the automaton cannot move on the empty stack, and blocks. This means if it did not just accept its input, it cannot continue and the computation fails. (Be aware, not all books agree on the precise details here.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.