I am stuck at the following problem:

Prove that if $L$ is a regular language over some alphabet $\Sigma$ and that $\sigma, \tau \in \Sigma$, Then the language $replace(L,\sigma,\tau)$ is regular.

Where $replace(L,\sigma,\tau)$ is defined as:

$replace(L,\sigma,\tau) = \{x\tau y\in \Sigma^*| x\sigma y\in L\}$.

My try:

Since $L$ is a regular language there exists a deterministic finite automaton $A=(\Sigma, Q, q_0, F, \delta_A)$ such that $L(A)=L$.

Now for each state $s\in Q$ we will define a non deterministic finite automaton $B_s=(\Sigma\cup\{\gamma\}, Q\times \{1,2\}, q_s, F\times \{2\}, \delta_{B_s})$ where $\gamma\notin \Sigma$ such that:

$\forall p\in Q,\mu\in\Sigma, \delta_{B_s}((p,1),\mu)=\{(\delta_A(p, \mu),1)\} $

$\forall p\in Q-\{s\}, \delta_{B_s}((p,1),\gamma)=\emptyset$


$\forall p\in Q,\mu\in\Sigma, \delta_{B_s}((p,2),\mu)=\{(\delta_A(p, \mu),2)\} $

$\forall p\in Q, \delta_{B_s}((p,2),\gamma)=\emptyset$

Now we'all define a new non deterministic finite automaton with $\epsilon$ moves $B$ by linking he starting state of this automaton to all of the starting states of the automatons $B_{s}$ for every state $s$, And we will also link the final states of all of the $B_{s}$ automatons to the final state of the automaton $B$.

The automaton $B$ will satisfy the property $L(B)=\{x\gamma y|x\sigma y\in L\}$ ( This is probably incorrect!!!)

Now we will define an homomorphism $h:\Sigma\cup\{\gamma\}\longrightarrow\Sigma$ such that:

$\forall \mu\in\Sigma,h(\mu)=\mu$


Since regular languages are closed under homomorphisms we can conclude that $h(L(B))$ is regular, But $h(L(B))=h(\{x\gamma y|x\sigma y\in L\})=\{x\tau y|x\sigma y\in L\}$ and so $replace(L,\sigma,\tau)$ is regular over $\Sigma$.

Thanks for any hint or help.

  • $\begingroup$ Which kind of other closure properties can you exploit? That against (finite-state) transduction would help, for instance. $\endgroup$
    – Raphael
    Apr 1, 2016 at 5:48
  • 1
    $\begingroup$ What is your question? We don't do homework checking. $\endgroup$
    – Raphael
    Apr 1, 2016 at 5:49

2 Answers 2


Let $A$ be the alphabet and let $a$, $b$, $c$, ... be the letters (this is easier to type).

Hint. Consider the (non-deterministic) transducer $A^* \to A^*$ defined by $1 \xrightarrow{c \mid c}1\xrightarrow{a \mid b} 2 \xrightarrow{c \mid c} 2$ (more precisely, there are transitions $1 \xrightarrow{c \mid c} 1$ and $2 \xrightarrow{c \mid c} 2$ for any letter $c$ of $A$, including $a$ and $b$, but there is a single transition form $1$ to $2$). For each transition, the left hand part of the label is the input letter, the vertical bar is a separator and the right hand part is the output letter.


Use closure properties. Define homomorphisms $h_1$ and $h_2$ as follows:

$\begin{align*} h_1(x) &= \begin{cases} x & x \in \Sigma \\ \sigma & x = A \text{ (a new symbol)} \end{cases} \\ h_2(x) &= \begin{cases} x & x \in \Sigma \\ \tau & x = A \end{cases} \\ \end{align*}$

Then $h_2(h_1^{-1}(L) \cap (\Sigma^* A \Sigma^*))$ does the trick.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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