proving that $L_\text{almost}$ is a regular language

Question

Let $L$ be a regular language. We will define:
$$L_\text{almost} = \{ w'\mid \exists w\in L\ \text{such that $w'$ is almost similar to }w \} $$
A word $w'$ is almost similar to $w$ if they are in the same length, and the difference between them is by one letter. for example: $abc$ and $abb$.

Prove that $L_\text{almost}$ is a regular language.

Ok, so I need to prove this by finding automata $M'$ that accepts $L_\text{almost}$. This is what I thought of:
$L$ is a regular language, so there is an automata $M$ which accepts it.
I thought of building $M'$ from $M$, and add parallel states to it for each state at $M$.
i.e., for every $q_i \in Q$, I will add $q'_i$ at $Q'$. The transitions for a word $w'\in L_\text{almost}$ will be just like at $M$, with one difference: if $w=a_1\ldots a_i\ldots a_n\in L$ and $w'=a_1\ldots a'_i\ldots a_n \in L_\text{almost}$, instead of going from $q_{i-1}$ to $q_i$ we will go to $q'_{i}$. From $q'_{i}$, we will proceed just like we would have done it at from $q_i$ at M, but on parallel states at $M'$. For $w=a_1\ldots a_n \in L$, this is the automata I thought of ($a'_i ≠ a_i$ for all $i$):

problem is that I don't know how to define the transition function for $M$. it seemed easy to me when I looked only at $w$, but I just can't describe at for $L$.
How can I define it here? or maybe there is a better way for approaching this question?

Answer 1

Suppose $\Sigma = \left \{0,1 \right \}$. Let $M'$ be a $NFA$ such it has two copy of states of $M$ like $Q_1$ and $Q_2$. Now if $q_i\in A$ for $DFA$ $M$, then $q_i^2\in A'$and :$$\delta(q_i,\sigma)=q_j \Rightarrow \delta '(q^2_i,\sigma)=\left \{ q^2_j \right \}$$ Let $\delta (q_i,0)=q_j$ and $\delta (q_i,1)=q_r$ then: $$\delta '(q^1_i,0)=\left \{ q^1_j,q^2_r \right \}$$ and $$\delta '(q^1_i,1)=\left \{ q^1_r,q^2_j \right \}$$ So we have $M'=<Q_1 \cup Q_2,\Sigma,q^1_0,A',\delta '>$It is easy to see that $L_{almost}=L(M')$. Also this construction can be extend for $|\Sigma|>2$ case.

Answer 2

Let $\mathcal{A} = (Q, A, \cdot, i, F)$ be a deterministic automaton recognising your language. For each pair of states $(p, q)$, let $L_{p,q}$ be the language recognised by the automaton $(Q, A, \cdot, p, \{q\})$. Thus $L_{p,q}$ is the set of labels of all paths from $p$ to $q$. By construction, each language $L_{p,q}$ is regular. Let $T$ be the set of transitions of $\mathcal{A}$. Thus $T = \{ (p,a,q) \in Q \times A \times Q \mid p \cdot a = q \}.$ Let $$ R = \bigcup_{(p,a,q) \in T} \bigcup_{f \in F} L_{i,p}AL_{q,f} $$

Claim. $L_\text{almost} = R$.

Indeed, let $w \in L_\text{almost}$. By definition, there exist some words $u$ and $v$ and two letters $a$ and $b$ (possibly equal) such that $w = ubv$ and $uav \in L$. Let $p = i\cdot u$, $q = p \cdot a$ and $f = q \cdot v$. By construction, $u \in L_{i,p}$, $b \in A$, $v \in L_{q,f}$, $(p,a,q) \in T$ and $f \in F$. Thus $w \in R$.

Let now $w \in R$. Then there exist some states $p, q \in Q$ and $f \in F$ and some transition $(p,a,q) \in T$, such that $w \in L_{i,p}AL_{q,f}$. It follows that $w = ubv$ for some $u \in L_{i,p}$, $b \in B$ and $v \in L_{q,f}$. Now $i \xrightarrow{u} p \xrightarrow{a} q \xrightarrow{v} f \in F$, which means that $uav \in L$. Consequently, $w \in L_\text{almost}$, which proves the claim.

It follows that $L_\text{almost}$ is regular.

Answer 3

Ok, I think I figured it out: $M=<Q,Σ,δ,s,A>$.
so for M' (which will be an NFA):

Q'=Q\A ∪ {q'|q∈Q}, s'=s, A'={q'|q∈A}
now the transition function ∆:
let it be $q$∈Q, a∈Σ. lets mark $q_r$=δ(q,a) ($q_r$∈Q).
so for every (q,a), so that $q$∈Q, a∈Σ the definition for ∆ will be:

∆(q,a)= δ(q,a)=$q_r$
∆(q',a)=$q'_r$
∆(q,a')=$q'_r$ , whereas a'≠a.

Is this definition correct?