I am reading "Introduction to the Theory of Computation" 3rd edition ~ by Michael Sipser, page 113-114 - topic: "Context free languages, push down automata"
He states that the transition from one state to another would look as follows: "$a,b\rightarrow c$". But the way he states the usage confuses me
We write "$a,b \rightarrow c$" to signify that when the machine is reading an $a$ from the input, it may replace the symbol $b$ on the top of the stack with a $c$. Any of $a,b \ and \ c"$ may be $ε$
If $a$ is $ε$, the machine may make this transition without reading any symbol from the input
If $b$ is $ε$, the machine may make this transition without reading and popping any symbol from the stack
If $c$ is $ε$, the machine does not write any symbol on the stack when going along this transition
My question is what would happen in the following cases:
- When $b$ is $ε$, and $c$ is $ε$
- When $b$ is $ε$ and $c$ contains a symbol
- When $b$ contains a symbol and $c$ is $ε$
- When $b$ contains a symbol and $c$ contains a symbol, where both symbols are different
- When $b$ contains a symbol and $c$ contains a symbol, where both symbols are same
My understanding is as follows: if $b$ is $ε$ then we "push" a symbol on stack, if $c$ is empty then we "pop" a symbol from the stack and when he says $a,b \rightarrow c$ he means, given $b$ is not $ε$, "if" $b$ is the top symbol of the stack then we can either pop or replace, and my answers to the above questions are as follows:
- Push operation: Push empty string on stack, meaning make no changes to the stack ( not sure about this one because both $b$ and $c$ are $ε$ so it could be a push + pop operation??, clarify please this especially )
- Push operation: Push the symbol $c$
- Pop operation: Pop the top symbol $b$ from the stack
- Replace operation: Replace the top symbol that is $b$ with $c$
- Replace operation: Replace the top symbol that is $b$ with $c$, in this case the stack will remain the same