1
$\begingroup$

This question has been quite confusing me. $\sum = \{a,b,c\}, L \text{ is a regular language}$ and we have to prove that $L^{'} = \{w \in L : w\text{ containts at least one c} \}$ is regular.

What are the steps of the proof? What methods can we use? I am new to automata and I have suggested the following which I am sure would not work:

$L$ is regular, then it has a regular expression $r \rightarrow L(r) = L $. Now if we write the expression $(r \cdot c \cdot c^* \cdot r^*)$ then it is a regular expression of the language $L^{'}$ where we would have a word of the language $L$ and also the word would contain at least one $c$.

I can deeply sense that there is a big flaw in that, what did I do wrong? and can you please direct me into a good solution?

Thank you!

$\endgroup$
1
$\begingroup$

Consider the regular language $K = \Sigma^*c\Sigma^*$. Then your language $L'$ is equal to $L \cap K$. You should have learnt that regular languages are closed under intersection, so $L'$ regular.

$\endgroup$
  • $\begingroup$ Could you please explain why $K$ is indeed a regular language? $\endgroup$ – TheNotMe Oct 29 '13 at 9:45
  • $\begingroup$ @TheNotMe: $K$ is regular because you have a regular expression for it: $\Sigma^*c\Sigma^*$. If $\Sigma=\{a_1,\ldots,a_n\}$, that’s $(a_1+\ldots+a_n)^*c(a_1+\ldots+a_n)^*$ (or whatever symbol you use instead of $+$ to indicate a choice of symbols). $\endgroup$ – Brian M. Scott Oct 29 '13 at 9:47
  • $\begingroup$ $K$ is given by a regular expression, so it is regular. $\endgroup$ – J.-E. Pin Oct 29 '13 at 9:48
2
$\begingroup$

Consider the language $L$ generated by the regular expression $caa^*$: $L$ consists of all words of the form $ca^n$, where $n\ge 1$. In this case your regular expression $rcc^*r^*$ is $caa^*cc^*(caa^*)^*$, which does not generate any word in $L$: every word that it generates contains at least two $c$’s, while every word in $L$ contains exactly one $c$.

I suggest that instead of approaching the problem via regular expressions, you approach it via automata. Since $L$ is regular, there is a DFA $M$ that accepts $L$; try to modify $M$ so that it accepts only those words of $L$ that contain at least one $c$. I’ll outline one way to do this, leaving most of the details to you. Make two copies of $M$, say $M_1$ and $M_2$; $M'$, the new DFA, will be built from $M_1$ and $M_2$. The initial state of $M_1$ is the initial state of $M'$, and the acceptor states of $M_2$ are the acceptor states of $M'$. $M'$ has no acceptor states in $M_1$. The transitions in $M_2$ remain unchanged, as do the transitions in $M_1$ for all inputs except $c$. If $M_1$ has a $c$ transition from a state $p$ to a state $q$, remove that transition and replace it with one from $p$ to the copy of $q$ in $M_2$. The idea is that as soon as $M'$ receives a $c$ input, it switches over from running in $M_1$ to running in $M_2$. Since the acceptor states are all in $M_2$, it can accept only words that contain at least one $c$. However, the design ensures that it accepts only words in $L$.

$\endgroup$
  • $\begingroup$ Great approach! Thanks alot! $\endgroup$ – TheNotMe Oct 29 '13 at 9:44
  • $\begingroup$ @TheNotMe: You’re welcome! $\endgroup$ – Brian M. Scott Oct 29 '13 at 9:48

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.