Suppose that D ∈ [[M]] + and let ρ be an accepting run of M on D. is still acyclic (because e 1 and e 2 belong to distinct connected components of D) and ρ is an accepting run on D[e 1 ↔ e 2 ] as well.
now, let us turn M into M by adding a unique leaf symbol , adding a new state f and the transition {f } − → ∅, and turning all original transitions of the form the DAGs recognized by M are those originally recognized by M, but with additional leaves labeled added as leaves below the original leaves, and the accepting runs of M are those of M, extended by labeling the (unique) outgoing edges of the original leaves with f .