proposition: Lemma length_preserving_M' : length_preserving M'.
proof: Proof. Proof using length_preserving_M lp_XY Y_fresh XY_neq. move=> >. rewrite /M' in_app_iff. move=> [[|[|]]|]. - move=> [] *. by subst. - move: lp_XY => [? ?] [] *. subst. constructor; [done | by lia]. - done. - by move /length_preserving_M. Qed.
imports: Relation_Operators Operators_Properties List Lia PeanoNat Undecidability.StackMachines.SMN Undecidability.StackMachines.Util(List_facts SMN_facts) ssreflect ssrbool ssrfun