patternMinor
Can you pop 2 elements at a time in a PDA
Viewed 0 times
canelementsyoutimepdapop
Problem
My question is N(a)=2N(b) ; No of a's = 2 * No of b's . So for every symbol b can I pop 2 a's simultaneously
Solution
In the usual definition of pushdown automata, at every step the PDA pops a stack symbol and reads an input symbol, and based on that it pushes a string of symbols (zero or more) onto the stack, and transitions to a new state (possibly non-deterministically, i.e. there could be several or no choices). If you define PDAs according to this definition then you cannot pop two stack symbols in a single transition.
That said, you can simulate popping two symbols using epsilon transitions (exercise). Therefore, the variant of PDAs in which you are allowed to pop more than one stack symbol is equivalent in power to a standard PDA.
That said, you can simulate popping two symbols using epsilon transitions (exercise). Therefore, the variant of PDAs in which you are allowed to pop more than one stack symbol is equivalent in power to a standard PDA.
Context
StackExchange Computer Science Q#65489, answer score: 7
Revisions (0)
No revisions yet.