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!
Best Answer
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$.