Question: The "pushdown store," or "stack," is a storage structure that operates much like a set of plates stacked on a spring in a cafeteria. All storage locations are initially empty. An item of data is added to the top of the stack by a "push" instruction, which pushes any previously stored items farther down in the stack. Only the topmost item on the stack is accessible at any moment, and it is fetched and removed from the stack by a "pop" instruction. Let's consider strings of integers that are an even number of characters in length; half the characters are positive integers, and the other half are zeros. We process these strings through a pushdown store as follows: As we read from left to right, the push instruction is applied to any nonzero integer, and a zero causes the pop instruction to be applied to the stack, thus printing the popped integer. Thus, processing the string 12030040 results in an output of 2314, and processing 12304000 results in an output of 3421. (A string such as 10020340 cannot be handled by this procedure because we cannot pop two integers from a stack containing only one integer.) Both 2314 and 3421 can be thought of as permutations,
respectively, on the set A = 51, 2, 3, 46.
a. What permutation of A = 51, 2, 3, 46 is generated by applying this procedure to the string 12003400?
b. Name a permutation of A = 51, 2, 3, 46 that cannot be generated from any string where the digits 1, 2, 3, and 4 appear in order, no matter where the zeros are placed.