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 '16 at 5:48
  • 1
    $\begingroup$ What is your question? We don't do homework checking. $\endgroup$ – Raphael Apr 1 '16 at 5:49

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.


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.