How to prove that $\{\$x\$\}$ is a regular language if $x$ is derived from $L=\{w\}$ by substituting substrings?

Question

Prove that if $L$ is regular over $\Sigma=\{0,1,2\}$ then the following language over $\{0,1,2,\$\}$ is also regular: $$ G=\{\$x\$|\exists w\in L: x\text{ is derived from }w\text{ by substituting } 01 \text{ with }\$\$ \} $$ For example, if $10112\in L$ then $\$1\$\$12\$\in G$.

I think this can be solved using closure properties of regular languages.

1) Let $H=\$L\$$. $H$ is also regular because it's concatenation.

2) Let $h:\Sigma\to \Sigma^*$ be defined as follows: $$ h(\$)=h(0)=h(1)=\$ $$ Then: $$ G=h^{-1}(H)\cap \$(\Sigma^*\$\$\Sigma^*)^+\$ $$ which is regular because $h^{-1}$, intersection and regular expressions are closed in regular languages.

---

I wonder if my proof using closure is correct or automaton should be built in this case? In addition if I managed to think of a regular expression to describe $G$ then this alone would've proved that $G$ is regular?

Answer 1

Unfortunately, your argument breaks down at step 2). For example, let $L=\{01\}$. Then
$G =\{\$\$\$\$\}.$
$H=\{\$01\$\}$.
$h^{-1}(H)=\emptyset$ since every word in the range of $h$ contains neither 0 or 1.
$h^{-1}(H)\cap \$(\Sigma^*\$\$\Sigma^*)^+\$=\emptyset.$
However, $G$ is not empty.

---

If I managed to think of a regular expression to describe G then would this alone have proved that G is regular?

Of course. However, it looks like it is not immediate to figure out a regular expression for $G$ even if we have been given the regular expression for $L$ and DFA for $L$.

---

Here is a way to show $G$ is regular by DFA.

Let the DFA for $L$ be $(\Sigma,Q, q_0,\delta_L, F)$.

Define (an incomplete) DFA $D$ with alphabet $\{0,1,2,\$\}$, states $Q\times \{s_0, s_1, o\}$, initial state $(q_0, s_0)$, accepting state $F\times\{s_0, o\}$, transition function $\delta_D$ such that
$\delta_D((q, s_0), 0)= (\delta_L(q, 0), o) $
$\delta_D((q, s_0), 1)= (\delta_L(q, 1), s_0) $
$\delta_D((q, s_0), 2)= (\delta_L(q, 2), s_0) $
$\delta_D((q, s_0), \$)= (\delta_L(q, 0), s_1) $

$\delta_D((q, s_1), \$)= (\delta_L(q, 1), s_0) $

$\delta_d((q, o), 0)= \delta_L(q, 0), o) $
$\delta_d((q, o), 2)= \delta_L(q, 2), s_0) $
$\delta_d((q, o), \$)= \delta_L(q, 1), s_1) $

Here is how we can understand the states

• state $(q,o)$ corresponds to the states that are reached by words that end with $0$.
• state $(q,s_1)$ corresponds to the states that are reached by words that end with odd number of $\$$'s.
• state $(q,s_0)$ corresponds to the states that are reached by words that end with $1$ or $2$ or even number of $\$$'s.

We can check that $G=\$L(D)\$$.

---

Exercise. Prove that if $L$ is regular over $\Sigma=\{0,1\}$ then the following language over $\{0,1,2\}$ is also regular. $$ G=\{x\mid \exists w\in L: x\text{ is derived from }w\text{ by substituting } 00 \text{ and } 11 \text{ with } 2 \text{ from left to right} \}$$ For example, if $w=1000111110$, then $x=1202210$.