0
$\begingroup$

I am currently constructing pushdown automata. can I push/pop alphabet more than two in a transition??

For example, $\delta$(a, a/aaa) means, in the state of input alphabet 'a' and stack point 'a' (there is only one item 'a') then it can push two more item 'a' on the stack so that there is three a's in the stack.

$\endgroup$
1

1 Answer 1

1
$\begingroup$

This depends on the formalism you are using.

As a "abstract data structure" you would have simple instructions like push(symbol), pop, top, isempty that you then can program as an add-on to a finite state automaton.

In standard formal language theory one uses a single instruction of the form you describe $(p,a,A,q,\gamma) \in \delta$ means: in state $p$ with $A$ on top of the stack we can pop $A$ and push the symbols $\gamma$ and move to state $q$. Thus we can indeed push several symbols at once, and we always pop one. With this single instruction we can also pop a symbol (by not pushing anything back) or keep the stack unchanged (by pushing back what has been popped).

In the Sipser book the formalism is different for instance.

$\endgroup$

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.