Where to put the state in a two-stack push down automaton?

theoretically, the state is between the two kleene-stars of the work-alphabet

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

• excuse me, is the edit of my question your answer to my question? first I don't find this a good way. second, the answer should be more specific: where exactly is the state saved? Commented Jan 13, 2021 at 15:10
• What do you mean by "where to put a state" and "middle with the state"? Can you elaborate or clarify your question? Commented Jan 13, 2021 at 17:24
• Sure. On a one-tape turing-machine the state has a certain position such that you have one side "left of the current state" and a side "right of the curent state". See wikimedia.org/api/rest_v1/media/math/render/svg/… I imagine the two stacks to be the "left side" or the "right side" of the state written on the tape. And with LR-Parsers for example it is in every source absolutely made clear, where the states (of the dfa) are saved. In every source known to me on tspda's however it is in every source absolutely unspoken of where to save the state Commented Jan 14, 2021 at 3:03
• Your question is still unclear. Are you talking about configurations? Commented Jan 14, 2021 at 9:37
• You are correct, it's a notation for the configuration of a TM. But I thought the notation would be adaptable to the question, where each of the two stacks begins and ends and I naively thought the first stack would end at the symbol for the current state and the other, analogously, would begin after the symbol for the current state. But maybe a tspda work completely different. And maybe I could conjecture how it works, when somewhere were mentioned, where the current state is recorded such that I could infer, what role it plays for the stacks or how they relate to each other better. Thanks. Commented Jan 14, 2021 at 13:58

1 Answer

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.

• Dear Bader, thanks for your answer. Hold on, I accidentally pressed enter without shift. Commented Jan 15, 2021 at 16:48
• Your post is a good answer - but sadly to another question. However, thank you to begin with for your interest in helping me. But it made clear to me, that aqb is not how the state of a TM or TSPDA is recorded, but only a convention of how to write a configuration of the turing machine. That is, the state is NOT, as conjectured before, written on the worktape after/before the current letter, but is instead recorded someplace else. Commented Jan 15, 2021 at 16:53
• I will make a thread "What is the configuration of a TSPDA?", then you post your answer there and I accept it. Deal? Commented Jan 15, 2021 at 16:55
• Sadly, in the literature I can find, I cannot find a practical enough description that would deal with my question: How to record the current state. And arising thereby the question: How do the two stacks work. Because assuming that the state was "the middle", I would conjecture the two stacks to be the left and the right side of the state-symbol on the tape and a TSPDA thereby simulating movement of the head by popping a letter from on stack and pushing/shifting it on the other while changing the state symbol in the "middle" whatever this would be in two stacks. Commented Jan 15, 2021 at 16:59
• Im glad the answer clarified somethings. There is no need to make another thread. As you've noted we have conventions about encoding configurations, so it is still not clear to me what is the exact question. Can you define "record a state"? If your question is how the two stacks work, this is simple, I can add that to the answer. Commented Jan 15, 2021 at 17:15