parsing regex with HTML
it's (still, always, will never not be) crazy to me that two finite automata are reducible to one finite automaton but that two stacks is a turing machine.
but hmmm.......one stack's series of operations will always necessarily conform to the paired push–pop protocol. what is the "series of operations" for two?
well, imagine two work for some time, and each produce their own intermediate state (and allow negative push/pop). then the two are compared somehow (?)
why does single-stack paired push/pop achieve immediate solvability? because any previous intermediate state can be converted to any desired final state, by (if necessary) popping everything off then popping exactly the required order back on.
why does dual-automaton reduce? well, we can reframe it as "cartesian product of states, both moving at once". to transition to the desired final state from any intermediate state, each constituent automaton independently makes the same moves it would have alone. there is no move together that escapes the individual constraints, or vice versa.
two-stack with only one symbol is equivalent to one-stack one-sym i.e. an integer
in the case of overlapping stack syms (assume binary for both) the two may produce intermediate states that do not "unzip" or "match up" cleanly
oh oh oh i get it! (?)
the two stacks start from some left and right boundary towards each other in the center. on adjacent input indices, they have each now independently built up a stack (a bit string).
two interpretations:
(1) [adversarial] no matter what one stack does to achieve a desired final state, the other can thwart it. this is clearly true even if they both start with empty stack, and both decisions are made simultaneously.
(2) [goal] the desired final goal is to achieve a specific bit string composed of the left and the right stack's concatenated 1/0 contributions (ignore negatives).
the actual tape machine reduction (which was a challenge problem from jeremy spinrad to me many years ago, and which i just now discovered), is very similar to the above idea, but with the goal to produce a specific tape state.
so both come in from each side, generating the appropriate tape marks, and meet in the middle. however, the head of the tape machine must be at the correct index! but this is simple, by just identifying the distance from each boundary to the central head, and performing only up to those pushes
i think "linear language" is a better name than "finite-state language", because the matching is literally linear time and because there are no loops