# What (formal) language does this describe? And, how do I prove it's regular?

I have this problem that I can't seem to be able to wrap my head around, and I was wondering if there was someone here that could help me understand it.

Let $L_1$ be a regular language over $\{a, b, c\}$. We deﬁne

$\qquad L_2 = \{xy \in \{a, b, c\}^∗ \mid xay \in L_1 \vee xby \in L_1\}$.

For example, if $L_1 = \{a, abc, c\}$, then $L_2 = \{\lambda, ac, bc\}$. Prove that $L_2$ is a regular language.

I really don't understand what language $L_2$ is in the first place, which makes it very hard for me to prove its regularity...

Any help would really be appreciated!

-

## 2 Answers

L2 is the set of words that can be formed by deleting exactly one $a$ (or exactly one $b$) from a word in L1.

-
Wow, really?! Well, if you put it that way it's a lot easier :) thanks! –  Linus Oct 2 '11 at 15:08

If $L_1$ is regular there is a DFA $A$ accepting that language. Try to build another finite automaton from $A$ that is essentially the same but demands that exactly one $a$ or $b$ is "skipped" in any accepting run of $A$.

(Can you do it with this hint? If not, I can post details.)

-
Yeah, thanks a lot! I had sort of figured this out by myself after the first answer, but it's nice to see it confirmed by someone else :). Cheers! –  Linus Oct 2 '11 at 16:47