Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
up vote 1 down vote accepted

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

share|cite|improve this answer
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.)

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.