1
$\begingroup$

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?

Improve this question
$\endgroup$
1
$\begingroup$

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

Improve this answer
$\endgroup$
  • $\begingroup$ Can you please explain why do you have states based on what letter reached the end of the words? For example, I'd define the transition functions as follows: $$\delta_D((q,2),0)=(\delta(q,2),0)\\\delta_D((q,\$),0)=(\delta(q,0),1)\\\delta_D((q,\$),1)=(\delta(q,1),0)$$.In my example we start out with state $0$. When we read the first $\$$ we flip the state to $1$. When we read the second $\$$ we flip the state back to $0$. When we read $2$ nothing changes so we stay in state $0$ as well. In the end we can add $\$$'s from the beginning and end of each word. $\endgroup$ – Yos Jan 28 '19 at 20:38
  • 1
    $\begingroup$ If we know the last letters of the words that reaches a state $s$, then we can specified what will be the next state if the word is extended with another letter. Note that we must ensure words containing 01 and words with isolated $\$$ should not be accepted. $\endgroup$ – John L. Jan 28 '19 at 20:47
  • 1
    $\begingroup$ Exactly. That is why incomplete DFA is popular since there is no need to write any transition that goes to a dead state. In fact, we do not have to specify that dead state. $\endgroup$ – John L. Jan 28 '19 at 20:58
  • 1
    $\begingroup$ I understand the transitions now, thanks! I still don't why you concatenate dollar sign here: $\delta_D((q, s_1), \$)= (\delta_L(q, 1), s_0)\$$? $\endgroup$ – Yos Jan 28 '19 at 21:05
  • 1
    $\begingroup$ Updated with a few corrections of typos. $\endgroup$ – John L. Jan 28 '19 at 21:13

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.