Q is the current state, [a1a2...ai...an-1] is the input string; for convenience, a0 = [ and an = ] is defined The current position in the input, viz. i with 0 ≤ i ≤ n, is marked by underlining the respective symbol. [Z1X2...Xj...Xm-1] is the stack, including substacks; for convenience, X1 = [Z1 and Xm = ] is defined. The current position in the stack, viz. j with 1 ≤ j ≤ m, is marked by underlining the respective symbol. Example An example run (input string not shown): Properties When automata are allowed to re-read their input ("two-way automata"), nested stacks do not result in additional language recognition capabilities, compared to plain stacks. Gilman and Shapiro used nested stack automata to solve the word problem in certain groups. Notes References Models of computation Automata (computation)