"Sea $\Sigma=\{a, b\} . $ Para cada palabra $ w=a_{1} \ldots a_{n} \in \Sigma^{*} $ con $ a_{i} \in \Sigma $ y $ 1 \leq k \leq n $ sea $ w_{k}^{-}:=a_{1} \ldots a_{k-1} \overline{a_{k}} a_{k+1} \ldots a_{n} $, mientras que $ \overline{a_{k}} $ es el carácter único de $ \Sigma \backslash\left\{a_{k}\right\} $. Para cada lenguaje $ L $ sobre $ \Sigma $ definimos el lenguaje $ L^{-} $ como $$L^{-}:= \left \{u \in \Sigma^{*} \mid u=w_{k}^{-}, k \in \mathbb{N} \text { y } w \in L \backslash\{\varepsilon\}\right\}$$ Muestre que la clase de lenguajes regulares está cerrada bajo la eliminación de caracteres. Es decir, para un autómata finito dado $ \mathcal{A} $ construya un nuevo autómata que acepte $ (L(\mathcal{A}))^{-} $."
No entiendo cómo podría resolver este problema sin saber un lugar específico en una palabra donde se debe omitir un carácter y cuál es ese carácter. He pensado en usar transiciones con $$, pero eso no garantiza que se haya omitido un carácter específico. Además, podría ser una pregunta tonta, pero en una palabra como $ w_{k}^{-}:=a_{1} \ldots a_{k-1} \overline{a_{k}} a_{k+1} \ldots a_{n} $, ¿no se convierte simplemente $a_{k+1}$ en el nuevo $a_{k}$ cuando se omite?
¡Cualquier ayuda sería muy apreciada! (Disculpe si la redacción es extraña, el idioma original del problema no era inglés.)
Problema en el idioma original:
"Se $ \Sigma=\{a, b\} . $ Para cada palabra $ w=a_{1} \ldots a_{n} \in \Sigma^{*} $ con $ a_{i} \in \Sigma $ y $ 1 \leq k \leq n $ sea $ w_{k}^{-}:=a_{1} \ldots a_{k-1} \overline{a_{k}} a_{k+1} \ldots a_{n} $, donde $ \overline{a_{k}} $ es el carácter único de $ \Sigma \backslash\left\{a_{k}\right\} $. Para cada lenguaje $ L $ sobre $ \Sigma $ definimos la omisión $ L^{-} $ como $$L^{-}:=\left\{u \in \Sigma^{*} \mid u=w_{k}^{-}, k \in \mathbb{N} \text { y } w \in L \backslash\{\varepsilon\}\right\}$$ Muestre que la clase de lenguajes reconocibles por autómata finito está cerrada bajo la omisión. Es decir, construya para un autómata finito dado $ \mathcal{A} $ un nuevo autómata que reconozca $ (L(\mathcal{A}))^{-} $."
Enfoque:
Sea $ L $ aceptado por el $ N F A \quad A=\left(Q, \Sigma, \Delta, q_{0}, F\right) $ , $ L(A)=L . $
Definimos el $ \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} $$ Prueba: $$ "\subseteq " $$ Sea $ w=a_{1} \ldots a_{n} $ una palabra en $L\left(A^{\prime}\right) $. Sea $ \left(q_{0}, a_{1}, \ldots a_{k-1}, r_{k-1}, \varepsilon, r_{k}, a_{k+1}, \ldots, a_{n}, q_{n}\right) $ una ejecución aceptada de $ w $. Entonces $ q_{n} \in F^{\prime} $ y $ \left(r_{i-1}, a_{i}, r_{i}\right) \in \Delta^{\prime} $ para cada $ i \in[1, n] \backslash k \mid 1 \leqslant k \leqslant n $
