The M2 constructor

Enter (Q, Σ, Γ, δ, q₀, qaccept, qreject),w. Use braces for sets and parentheses for tuples. Optional outer angle brackets are accepted.

• Write each transition as ((state,read),(nextState,write,L)) or use R. For example, ((q0,1),(q1,1,R)) means: in q0 reading 1, write 1, move right, and enter q1.
• _ means blank, not a space. Γ must contain it. Do not append blank cells or an ellipsis to w.
• Σ contains single digits; w uses only symbols in Σ. Use eps, ε, or nothing after the final comma for the empty word.
• State and tape-symbol names may contain letters, digits, and underscores. Declare a transition for every nonhalting state and tape symbol. Accept and reject states have no outgoing transitions.
• The tape extends to the right. A left move at its first cell stays at that cell.

1. Check whether x belongs to {0ⁿ1ⁿ | n ≥ 0}. The empty word qualifies.
2. If it does, accept.
3. Otherwise, erase x, write the fixed word w, and simulate M. Accept when M accepts; reject when M rejects. If M loops, M2 loops too.

M2 has input alphabet {0,1}. Its output includes extra states and tape symbols for checking, cleanup, and simulation. The constructor generates transitions; it does not run M on w.

For the supplied example, M accepts 11011, so the generated M2 accepts every binary input.