# If L is a regular language, how to prove that L' is also regular?

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.

• Hint: use closure properties of REG. – Raphael Apr 28 '16 at 11:44
• It sounds like you're aiming for a constructive proof. That is to say, a proof in the form of "An X exists, because here I have an example of an X". In particular, you try to come up with an example NFA for L'. There are also non-constructive proofs, such as "An X exists, because else ..." (proof by contradiction). – MSalters Apr 28 '16 at 13:44

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.

• I am sorry, but can you elaborate more your answer? It is not clear what are your hints. – Leonardo Lima Apr 27 '16 at 21:18
• @LeonardoLima I think the hints are very apt and very clear. The rest is your homework. – Raphael Apr 28 '16 at 11:44
• Do you need to remember what you've seen? It appears there's just a single reject state, and all other states are "Not rejected (yet)". Things become more complex if the language L' is defined as "L with at most N occurances of σ". That said, the NFA modification may make certain states of L' unreachable, which were reachable in L only via input σ. – MSalters Apr 28 '16 at 13:49

As Hendrick alluded, here are a couple of hints, assuming that the alphabet of $L$ is $\Sigma$:

1. Can you show that the language of all strings over $\Sigma$ containing a particular $\sigma\in\Sigma$ is regular? (A two-state DFA will do it.)
2. What do you know about the intersection of two regular languages?
• Can you point me the difference between the language mentioned in 1 and $L_{}{'}$? I can't see it. Yes, I know that the intersection of two regular languages is also a regular language, but I can't see your point here, sorry about that. – Leonardo Lima Apr 27 '16 at 21:35
• @LeonardoLima Dito. – Raphael Apr 28 '16 at 11:45
• The language in 1 (let's call it $M$) is the set of all strings over $\Sigma$ containing at least one $\sigma\in\Sigma$. $L'$ is the set of all strings in $L$ containing at least one $\sigma$. In other words, $L'=L\cap M$. – Rick Decker Apr 28 '16 at 14:58