Proving that a regular language is closed under a unique definition of 'reverse'

Question

Heyy guys, I was given the next question in one of my homework assignments and I can't quite figure out how to approach it. I'd really appreciate some help with it. Thank you!

Answer 1

If you've been given a question like this, you've probably seen some closure properties of regular languages. In particular, you may know that regular languages are closed under union, intersection, complementation, reversal, substitutions, and homomorphisms.

Some of these closure properties are usually proved by showing how to build an automaton that accepts the transformed language; others are proved by showing how to write a regular expression for the transformed language.

A classic example of the latter type of proof is the one for closure under substitutions. If $\mu$ is a map from alphabet $\Sigma$ to the regular languages over alphabet $\Gamma$, and $r$ is a regular expression over $\Sigma$, then replacing every letter $\sigma$ in $r$ with a regular expression for $\mu(\sigma)$ yields the desired regular expression.

In the case of $\operatorname{Inv}(L) = \{\, xyz : xy^Rz \in L \,\}$, though, we must be able to replace an arbitrary subword of a word in $L$ with its reversal; an arbitrary subword may not be produced by a proper subexpression of the chosen regular expression for $L$ that we may reverse. For example, if $L = 0^*1^*$, we have that $00111001 \in \operatorname{Inv}(L)$ because $00001111 \in L$, and it's not clear how to manipulate $0^*1^*$ to get $0^*1^*0^*1^*$ or something equivalent.

So we turn to the other master technique for the proof of closure properties, namely the construction of an automaton for $\operatorname{Inv}(L)$ from an automaton for $L$. After all, this is the technique used to prove closure of regular languages under reversal, and the problem at hand shouldn't be too different.

Let's recall how we deal with reversal: given an $A_L$ that accepts $L$, we build an automaton $A_{L^R}$ that accepts $L^R$ by reversing the directions of all transitions and swapping initial and accepting states. If our definition of automata does not allow multiple initial states, we'll add a new initial state and a few $\epsilon$-transitions.

Let's see now what simple facts we know about $\operatorname{Inv}(L)$. Since $y$ may be the empty word, we have that $L \subseteq \operatorname{Inv}(L)$. Likewise, since $x$ and $z$ may be the empty word, we have that $L^R \subseteq \operatorname{Inv}(L)$. These inclusions suggest that we may use the automata for $L$ and $L^R$ as building blocks for the automaton that accepts $\operatorname{Inv}(L)$, connecting them with $\epsilon$-transitions.

I'll pause here, to give you a chance to finish the construction yourself.