2-Stack PDA ≡ Deterministic Turing Machine: String Matching w#w

1
Select a test string of form w#w and observe how both machines process it
2
Choose transitions from 4 options for each step - both PDA and DTM
3
Watch how the PDA uses BOTH stacks: left for storage, right for comparison
4
Verify both machines reach the same decision for string matching
Current Step: 0
Status: Ready
Mode: Both Machines

2-Stack Pushdown Automaton

Current State: q₀
Remaining Input: abba

Left Stack

(Stores first part w before #)
⊥

Right Stack

(Stores second part w after #)
⊥

Select PDA Transition

Select a transition to proceed with the PDA simulation.

Deterministic Turing Machine

Current State: q₀
Head Position: 0

Tape

(X=marked first part, Y=matching pairs, #=separator)
↑

Select DTM Transition