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?

  • $\begingroup$ 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. $\endgroup$
    – John L.
    Jan 27, 2022 at 18:41
  • $\begingroup$ 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$? $\endgroup$ Jan 28, 2022 at 2:24


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.