[Solved]: If L is a regular language, how to prove that L' is also regular?

Problem Detail: 

I've been trying to construct a proof of the following statement the whole day but I got stuck:

If $L$ is a regular language, the language $L_{}{'}$ consisting of all words in $L$ containing the letter $\sigma$ (where $\sigma$ is an arbitrary fixed letter in $\Sigma$) is also regular.

I know that the first thing to do is to construct an NFA that recognizes $L_{}{'}$ from the NFA that recognizes $L$, but I can't find a conversion that is general enough. It might me silly, but I think one just have to change the transition function. I hope you guys can give me some advice.

Asked By : Leonardo Lima

Answered By : Hendrik Jan

Yes, but changing the transition function also might involve changing the states. In this case, the states should "remember" whether we have seen the letter $\sigma$ in the past.

Alternatively, one can prove closure properties like this using well-known properties, like the fact that regular languages are closed under intersection. The language of all words containing the letter $\sigma$ is regular.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/56619

3.2K people like this

 Download Related Notes/Documents