Let it be L, a regular language. we will define:
$L_\text{almost} = \{ w'\mid \exists w\in L\ w' \text{ 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∈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$):

picture 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.


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$ , whereas a'≠a.

Is this definition correct?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.