# Regular Languages are closed under Scarne's Cut

This exercise come from Sipser (1.68).

In essence, show that if $$A$$ is regular, then $$CUT(A) := \{yxz | xyz \in A\}$$ is regular. I've managed to show that $$B = \{yx | xyz \in A\}$$ is regular. Furthermore, I've shown that $$SUFFIX(A) = \{z | xz \in A\}$$ is regular. My idea was to then say that $$CUT(A)$$ is precisely the concatenation of $$B$$ and $$SUFFIX(A)$$. However, the trouble I'm running into is that this operation will attach the "wrong" suffixes to a string. For instance, if $$A$$ is "strings in alphabetical order", then $$bad$$ will be in the concatenation of $$B$$ and $$SUFFIX(A)$$.

How can I complete this?

• If you are not familiar with the guessing technique, please read the parts of this answer of Yuval on how to prove a language is regular that explains that technique. Jan 27, 2022 at 18:41
• How did you show that $\{yx \mid xyz \in A\}$ is regular? If you used a construction with automata it can probably be extended to include the suffix $z$? Jan 28, 2022 at 2:24