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$):

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?


3 Answers 3


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$ , 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.