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?
If L is regular, so is $L-\{λ\}$?
1 Answers
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.
-
0@Cam: thanks for helping out! – 2012-02-11