patternMinor
Where to put the state in a two-stack push down automaton?
Viewed 0 times
thestackwhereputtwopushdownstateautomaton
Problem
theoretically, the state is between the two kleene-stars of the work-alphabet
where q is the current state and each
Yours,
von Spotz
gamma* q gamma*where q is the current state and each
gamma* is the content of one of both stacks. But where is "the middle" with the state? Regarding the one tape of the classical Turing Machine it is obvious.Yours,
von Spotz
Solution
A configuration of a TM is usually defined as $uq\sigma v$, where $u\sigma v$ is the tape's content up to a cell from which there are only blanks, $q$ is the current state, and the head of the machine points at the letter $\sigma$. So the place of the state $q$ in the configuration $uq\sigma v$ is there simply to indicate at which letter the head points. Generally, a configuration holds a snapshot of the model during its run, including all information that is relevant to carry out the computation one step at a time.
Now consider a two-stack PDA $\mathcal{A}$, and think how to defined a configuration of it. Here, unlike TMs, we always point (in each stack) at the top of the stack, and therefore an indication to the stacks contents is sufficient - storing where the heads point does not add valuable information to help us compute the next configuration, given the current one. Specifically, the necessary information a configuration of $\mathcal{A}$ needs to hold are:
1- the content of the two stacks.
2- the current state.
3- the input left to be read.
So, we can define a configuration as a word of the form $ u q v \# w$, where $u$ is the content of the first stack, $v$ is the content of the second stack, $q$ is the current state, $w$ is the input left to be read, and $\#$ is a special charecter to indicate the end of $v$ and the beginning of $w$. Please note that the fact that $q$ is between $u$ and $v$ is not crucial. We could have defined a configuration of $\mathcal{A}$ as $qu\#v\#w$, and that makes no difference as long as we agree on which definition we stick. Anyway, I think the later definition is closer to being standard.
Now consider a two-stack PDA $\mathcal{A}$, and think how to defined a configuration of it. Here, unlike TMs, we always point (in each stack) at the top of the stack, and therefore an indication to the stacks contents is sufficient - storing where the heads point does not add valuable information to help us compute the next configuration, given the current one. Specifically, the necessary information a configuration of $\mathcal{A}$ needs to hold are:
1- the content of the two stacks.
2- the current state.
3- the input left to be read.
So, we can define a configuration as a word of the form $ u q v \# w$, where $u$ is the content of the first stack, $v$ is the content of the second stack, $q$ is the current state, $w$ is the input left to be read, and $\#$ is a special charecter to indicate the end of $v$ and the beginning of $w$. Please note that the fact that $q$ is between $u$ and $v$ is not crucial. We could have defined a configuration of $\mathcal{A}$ as $qu\#v\#w$, and that makes no difference as long as we agree on which definition we stick. Anyway, I think the later definition is closer to being standard.
Context
StackExchange Computer Science Q#134247, answer score: 2
Revisions (0)
No revisions yet.