1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Hint: use closure properties of REG. $\endgroup$ – Raphael Apr 28 '16 at 11:44
  • $\begingroup$ 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). $\endgroup$ – MSalters Apr 28 '16 at 13:44
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I am sorry, but can you elaborate more your answer? It is not clear what are your hints. $\endgroup$ – Leonardo Lima Apr 27 '16 at 21:18
  • 1
    $\begingroup$ @LeonardoLima I think the hints are very apt and very clear. The rest is your homework. $\endgroup$ – Raphael Apr 28 '16 at 11:44
  • $\begingroup$ 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 σ. $\endgroup$ – MSalters Apr 28 '16 at 13:49
1
$\begingroup$

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?
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Leonardo Lima Apr 27 '16 at 21:35
  • $\begingroup$ @LeonardoLima Dito. $\endgroup$ – Raphael Apr 28 '16 at 11:45
  • 1
    $\begingroup$ 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$. $\endgroup$ – Rick Decker Apr 28 '16 at 14:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.