Show that the class of regular languages is closed under gapping "Let $\Sigma=\{a, b\} . $ For every word $ w=a_{1} \ldots a_{n} \in \Sigma^{*} $ with $ a_{i} \in \Sigma $ and $ 1 \leq k \leq n $ let $ w_{k}^{-}:=a_{1} \ldots a_{k-1} \overline{a_{k}} a_{k+1} \ldots a_{n} $, while $ \overline{a_{k}} $ is the unique character out of $ \Sigma \backslash\left\{a_{k}\right\} $.
For every language $ L $ over $ \Sigma $ let gapping $ L^{-} $ be defined by
$$L^{-}:= \left \{u \in \Sigma^{*} \mid u=w_{k}^{-}, k \in \mathbb{N} \text { und } w \in L \backslash\{\varepsilon\}\right\}$$
Show that the class of regular languages is closed under gapping. Meaning for a given finite automaton $ \mathcal{A} $ construct a new automaton that accepts $ (L(\mathcal{A}))^{-} $."
I don't understand how I could solve this problem without knowing a specific place in a word where one character is supposed to be left out and which character that is. I have thought about using $ε$- transitions, but that doesn't guarantee that a specific character has been left out.
Also this might be a dumb question but in a word like $ w_{k}^{-}:=a_{1} \ldots a_{k-1} \overline{a_{k}} a_{k+1} \ldots a_{n} $ doesn't $a_{k+1}$ just become the new $a_{k}$ when that is left out?
Any help would be greatly appreciated! (Sorry if the wording is weird, the original language of the problem wasn't English.)
Problem in original language:
"Sei $ \Sigma=\{a, b\} . $ Für jedes Wort $ w=a_{1} \ldots a_{n} \in \Sigma^{*} $ mit $ a_{i} \in \Sigma $ und $ 1 \leq k \leq n $ sei $ w_{k}^{-}:=a_{1} \ldots a_{k-1} \overline{a_{k}} a_{k+1} \ldots a_{n} $, wobei $ \overline{a_{k}} $ das eindeutige Zeichen aus $ \Sigma \backslash\left\{a_{k}\right\} $ ist.
Für jede Sprache $ L $ über $ \Sigma $ sei die Lückenbildung $ L^{-} $ definiert durch
$$L^{-}:=\left\{u \in \Sigma^{*} \mid u=w_{k}^{-}, k \in \mathbb{N} \text { und } w \in L \backslash\{\varepsilon\}\right\}$$
Zeigen Sie, dass die Klasse der FA-erkennbaren Sprachen unter Lückenbildung abgeschlossen ist. D.h. konstruieren Sie für einen gegebenen endlichen Automaten $ \mathcal{A} $ einen neuen Automaten, der $ (L(\mathcal{A}))^{-} $ erkennt."
ansatz:
Let $ L $ be accepted by the $ N F A \quad A=\left(Q, \Sigma, \Delta, q_{0}, F\right) $ , $ L(A)=L . $
We define $ \varepsilon-N F A \quad A^{\prime}=\left(Q^{\prime}, \Sigma^{\prime}, \Delta^{\prime}, q_{0}^{\prime}, F^{\prime}\right) $
$$ \begin{aligned} Q^{\prime} &=Q \\ \Sigma^{\prime} &=\Sigma \backslash\left\{a_{k}\right\}  \\ \Delta^{\prime} &=\left\{(q, \varepsilon, p) \mid\left(q, a_{k}, p\right) \in \Delta\right\} \end{aligned} $$
$$ \begin{aligned} F^{\prime}=F \end{aligned} $$
$$ \begin{aligned} L\left(A^{\prime}\right)=L^{-} \end{aligned} $$
Proof:
$$ "\subseteq " $$ Let $ w=a_{1} \ldots a_{n} $ be a word over $L\left(A^{\prime}\right) $.
Let $ \left(q_{0}, a_{1}, \ldots a_{k-1}, r_{k-1}, \varepsilon, r_{k}, a_{k+1}, \ldots, a_{n}, q_{n}\right) $ be an accepting run of $ w $.
Then $ q_{n} \in F^{\prime} $ and $ \left(r_{i-1}, a_{i}, r_{i}\right) \in \Delta^{\prime} $ for every $ i \in[1, n] \backslash k \mid 1 \leqslant k \leqslant n $
 A: Let $M=\langle Q,\Sigma,\delta,q_0,F\rangle$ be a DFA that recognizes $L$. We will construct an NFA $M'=\langle Q\times\{0,1\},\Sigma,\Delta,\langle q_0,0\rangle,F\times\{1\}\rangle$ that recognizes $\overline L$ for the interpretation in which $\overline{a_k}$ is the unique element of $\Sigma\setminus\{a_k\}$. For convenience let $\bar a=b$ and $\bar b=a$.
We can think of $M'$ as consisting of two copies of $M$, one with state set $Q\times\{0\}$, the other with state set $Q\times\{1\}$. $M'$ will start at $\langle q_0,0\rangle$ in the first copy, and at some point it will move to the second copy, which will behave exactly like $M$. Thus, we want
$$\Delta(\langle q,1\rangle,x)=\{\langle\delta(q,x),1\rangle\}$$
for each $q\in Q$ and $x\in\Sigma$.
The first copy will also behave like $M$, except that when it reads a symbol $x$, it has the option treating it as if it were $\bar x$ and moving to the appropriate state in the second copy of $M$. Thus, we want
$$\Delta(\langle q,0\rangle,x)=\{\langle\delta(q,x),0\rangle,\langle\delta(q,\bar x),1\rangle\}\,.$$
I’ll leave it to you to check that $M'$ really does recognize $\overline L$.
