patternMinor
Implementation details of "transitions" of Non-deterministic push-down automata
Viewed 0 times
transitionsnonautomatapushdowndeterministicdetailsimplementation
Problem
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:
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:
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
Solution
Kindly read again the description you have quoted from the book. It states there that $b$ is the stack element to be read and popped and $c$ would be the symbol to be pushed on top of the stack. So to answer your questions:
- Nothing will be popped and pushed
- Nothing will be popped but $c$ will be pushed
- Pop the stack and push nothing
- Pop the stack and push $c$
- Same as 4, as it doesn't matter if you pop and push the same symbol. You can think of this as the PDA inspecting (by popping) the top symbol and decided that this symbol is not yet meant to be popped in the current state, so it simply returned the popped symbol.
Context
StackExchange Computer Science Q#156990, answer score: 2
Revisions (0)
No revisions yet.