0
$\begingroup$

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 define

$\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 2

1

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

  • 0
    Wow, really?! Well, if you put it that way it's a lot easier :) thanks!2011-10-02
0

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

  • 0
    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!2011-10-02