Take the 2-minute tour ×
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.

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|improve this question
    
What does DFA mean? What is $L$? Can you give some context? Furthermore, the [homework] tag is used to signal the source of the problem is a homework assignment. Please add fitting tags describing the actual mathematical subject of the question. –  Asaf Karagila Feb 10 '12 at 23:11
    
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:51
    
@Pluto: no problem! Welcome to Math StackExchange! I hope you enjoy it here, and if you have any problems about how the site works, feel free to bring it up at our meta. –  Willie Wong Feb 11 '12 at 11:19

1 Answer 1

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

 
discard

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.