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

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?

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.

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.

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?