Question

Show that L is accepted by PDA in which no symbols are ever removed from the stack, then L is regular.

Answer 1

Answer:

Tim Farage, Professor, Computer Science Department, UT Dallas

Answered Jun 2, 2020 · Author has 4k answers and 7.4m answer views

If you have a stack in which no elements are ever removed, you don’t really have a stack. That’s all you have is memory for one item. And, because the number of stack symbols is always finite in a PDA, this one item can have only a finite number of values, so it doesn’t even act like memory.

Since this ‘lame’ memory can only store a finite number of values, they can be dealt with using an additional finite number of states.

For example, suppose your inputs are in {0,1}. And suppose your stack symbols are in {A,B,C}.

Then you can remove the stack, and add the stack symbols as inputs. Thus the inputs would be {0A, 0B, 0C, 1A, 1B, 1C}.

With those inputs no stack is needed, thus this becomes a FSA - and so the language L is regular.

Explanation: