Direct proof - DROP-OUT (A) is a regular language

Question

Proposition: Let A be a regular language over $\Sigma$. Define DROP-OUT(A) to be the language containing all strings that can be obtained by removing one symbol from a string in A. Thus, DROP-OUT(A) $= \{xz \mid xyz \in A,\ x,\ z \in Σ^{\ast}, y \in \Sigma\}$. Show that the class of regular languages is closed under the DROP-OUT operation.

Proof: Suppose $A$ is a regular language and $A = \{xyz \mid x,z ∈ Σ^{\ast}, y \in \Sigma\}$. Let xyz be an arbitrary word belonging to the language A and let X, Y and Z be regular languages ​​such that $X = \Sigma^{\ast}$, $Z = \Sigma^{\ast}$ and $Y = \Sigma$. Then, we have $x \in X$, $y \in Y$ and $z ∈ Z$. Thus, we have $xyz \in XYZ$, and since $xyz \in A$, it follows that $A \subseteq XYZ$. Now, we can build a new language by concatenating X and Z as follows, $W = XZ$. So, we built a language W starting from A, removing the language Y and concatenating as X and Z languages. As $W = XZ, xz \in W$ and $xz \in$ DROP-OUT(A) we can conclude that DROP-OUT(A) $\in W = XY$. Recall that regular languages are closed under concatenation. Therefore, as DROP-OUT(A) is formed by concatenation of two regular languages ​​we have that DROP-OUT(A) is a regular language. So if A is a regular language then DROP-OUT(A) is also regular.

Does my arguments suffices to prove that DROP-OUT(A) is a regular language?

Should I prior prove that X, Y and Z are regular languages too?

What can I do to improve it?

Answer 1

There are some major problems with your argument. First, $XYZ$ contains every word over $\Sigma$ that contains a $y$. It is entirely possible that $A$ contains words that do not contain $y$, in which case $A$ is not a subset of $XYZ$: from the fact that $xyz$ in $A$ you cannot conclude that $A\subseteq XYZ$. Your $W$ is simply $\Sigma^*$; it’s a subset of $\operatorname{DROP-OUT}(A)$ if and only if $\operatorname{DROP-OUT}(A)=\Sigma^*$. This certainly need not be the case.

Here’s an example that illustrates both problems. Let $\Sigma=\{x,y\}$; the language $A=\{x,xyx\}$ over $\Sigma$ is certainly regular, and it contains the word $xyx$, which is in your $XYZ$ with $X=Z=\Sigma^*$ and $Y=\{y\}$. However, $x\in A\setminus XYZ$, because $x\notin XYZ$. And $\operatorname{DROP-OUT}(A)=\{x\}$, which is very far from being $\Sigma^*$.

I do not at the moment see any way to repair this argument; I think that you need a fresh start. Like Phicar, I’d be inclined to argue via automata, though I might do it without $\epsilon$-transitions.