demostrando que $L_\text{almost}$ es un lenguaje regular

Question

Deja que sea L un lenguaje regular. vamos a definir:
$L_\text{almost} = \{ w'\mid \exists w\in L\ w' \text{ is almost similar to }w \}$
una palabra $w'$ es casi similar a $w$ si son de la misma longitud, y la diferencia entre ellos es por una letra. por ejemplo: "abc" y "abb".

demostrar que $L_\text{almost}$ es un lenguaje regular.

Ok, así que tengo que probar esto mediante la búsqueda de autómatas M' que acepta $L_\text{almost}$.
esto es lo que he pensado:
$L$ es un lenguaje regular, por lo que no es un autómata $M$ que la acepta.
Yo pensaba en la construcción de la M de M, y añadir en paralelo a los estados a que para cada estado en la M.
es decir, para cada $q_i∈Q$, voy a añadir $q'_i$$Q'$. las transiciones de una palabra $w'\in L_\text{almost}$ será igual a $M$, con una diferencia: si $w=a_1\ldots a_i\ldots a_n\in L$$w'=a_1\ldots a'_i\ldots a_n \in L_\text{almost}$, en lugar de ir de $q_{i-1}$ $q_i$vamos a ir a $q'_{i}$. de $q'_{i}$, procederemos igual que han hecho en la de $q_i$ a M, pero en paralelo a los estados a $M'$. para $w=a_1\ldots a_n \in L$, este es el autómata pensé de ($a'_i ≠ a_i$ todos los $i$):

el problema es que no sé cómo definir la transición de la función de $M$. parecía fácil para mí cuando miré sólo en $w$, pero simplemente no puedo describir a para $L$.
Cómo puedo definir aquí? o tal vez hay una mejor manera de abordar esta pregunta?

Answer 1

Supongamos $\Sigma = \left \{0,1 \right \}$. Deje $M'$ $NFA$ tal tiene dos copias de los estados de $M$ como $Q_1$$Q_2$. Ahora si $q_i\in A$ $DFA$ $M$, a continuación, $q_i^2\in A'$y el :$$\delta(q_i,\sigma)=q_j \Rightarrow \delta '(q^2_i,\sigma)=\left \{ q^2_j \right \}$$ Deje $\delta (q_i,0)=q_j$$\delta (q_i,1)=q_r$, entonces: $$\delta '(q^1_i,0)=\left \{ q^1_j,q^2_r \right \}$$ y $$\delta '(q^1_i,1)=\left \{ q^1_r,q^2_j \right \}$$ Así que tenemos $M'=<Q_1 \cup Q_2,\Sigma,q^1_0,A',\delta '>$es fácil ver que $L_{almost}=L(M')$. También esta construcción se puede extender para $|\Sigma|>2$ de los casos.

Answer 2

Ok, creo que lo he descubierto: $M=<Q,Σ,δ,s,A>$.
así que para M' (que será un NFA):

Q'=Q\A ∪ {p'|q∈Q}, s'=s'={p'|q∈A}
ahora la transición de la función de ∆:
vamos a ser $q$∈Q, a∈Σ. permite marcar $q_r$=δ(q,a) ($q_r$∈P).
así que para cada (p,a), de modo que $q$∈Q, a∈Σ la definición de ∆ será:

∆(q,a)= δ(q,a)=$q_r$
∆(q,a)=$q'_r$
∆(q,a')=$q'_r$ , mientras que un'≠a.

Es esta definición correcta?