'$L$ almost' is regular

Question

Given a regular language $L$, I have to prove that '$L$ almost' is regular where '$L$ almost' is all the words which differ from the words of $L$ by one char. for example, if $L = \{aab,aaa\}$, so $bab$ belongs to '$L$ almost' because it differs from $aab$ only by the first letter. I have found this problem's solution and I simply can not understand the transition function. If someone can explain it or maybe suggest a different one, that would be fantastic. The most difficult part is the part of $t$,$t'$ so if you can be explicit when it comes to this part I would appreciate that. Explanation of the picture (it's in Hebrew): $L$ is regular so there is a DFA $M$ which defines it. They are creating an NFA based on the DFA by making two copies of the DFA, and moving from one to the other. Any help understanding the transition function will do. Thank a lot in advance!

Solution

Answer 1

If $L$ is regular, then consider a DFA on $L$. Make two copies of it $D_1$ and $D_2$ and consider the DFA $D_1\cup D_2$ letting the start state of $D_1$ be the start state of $D_1\cup D_2$. Let $a_{(D_1)}$ and $b_{(D_1)}$ be states in $D_1$ and let $a_{(D_2)}$ and $b_{(D_2)}$ be the corresponding states in $D_2$. For all $a_{(D_1)}$,$b_{(D_1)}$,$a_{(D_2)}$ and $b_{(D_2)}$, if $\sigma\in \Sigma$ and $a_{(D_1)}$ transitions to $b_{(D_1)}$ on $\sigma$ in $D_1$, then we will add the transition $a_{(D_1)}$ to $b_{(D_2)}$ on any character except $\sigma$ (i.e. $\Sigma - \sigma$) to $D_1\cup D_2$. Remove the accept states from $D_1$ in $D_1\cup D_2$. This NFA accepts exactly "$L$ almost".

The idea is that for any word in $L$, we want to make one "error" (the one letter off from the word in $L$). In our NFA, if a word is in $L$, then it will transition entirely within $D_1$ in $D_1\cup D_2$. However, an "error" will then transition to the corresponding next state in $D_2$. This means that a word is in a state of $D_2$ in $D_1\cup D_2$ only if it has an "error". We want to accept only the words that have one "error", so we remove the accept states from $D_1$ (since a word will only end in $D_1$ if it is in $L$).