Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

A language is regular, by definition, if you can create a DFA for it. Then I need to prove that if $L$ is regular, then so is $L-\{\lambda\}$ for any $\lambda\in L$. Any ideas?

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

There are several ways of proving a language is regular. One, which by the wording of your question suggests was your first attempt, is to construct an explicit DFA which recognizes your language. In your problem, such an explicit construction is impossible since you do know the shape of the DFA that recognizes the original language $L$. Nevertheless, you could try to describe a procedure for taking a DFA for $L$ and explicitly describing how to modify the DFA to recognize $L-\{\lambda\}$. This would probably require a pretty intricate construction.

Alternatively, and much less painfully, is to use closure properties of regular languages. For example, the set of regular languages is closed under intersection and complements, and hence under set difference (why?). Since $\{\lambda\}$ is regular (why?) and $L$ is regular, so must be $L-\{\lambda\}$. Note that this latter approach is basically the same as the first approach, but sweeping all the messy DFA constructions into the proofs of the closure properties.

share|cite|improve this answer
This is my first time to use stack exchange. I will optimize my tag and explain abbreviations next time. But thank you for editing! – Pluto Feb 11 '12 at 6:54
@Cam: thanks for helping out! – Willie Wong Feb 11 '12 at 11:18

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.