[Solved]: Proving a specific language is regular

Problem Detail: 

In my computability class we were given a practice final to go over and I'm really struggling with one of the questions on it.

Prove the following statement:

If $L_1$ is a regular language, then so is

$L_2 = \{ uv |$ $u$ is in $L_1$ or $v$ is in $L_1 \}$.

You can't use the pumping lemma for regular languages (I think), so how would you go about this? I'm inclined to believe that it's false because if $u$ is in $L_1$, what if $v$ is non-regular? Then it would be impossible to write a regular expression for it. The question is out of 5 marks though and that doesn't seem like enough of an answer for it.

Asked By : user1217222

Answered By : Gilles

You can use the pumping lemma to show that a language is not regular. Here, you're trying to prove that if $L_1$ is regular then $L_2$ is regular. The pumping lemma can't be used to prove this implication. It could be used to prove the contraposite (i.e. you might be able to prove that if $L_2$ is not regular, then $L_1$ is not regular by the pumping lemma). However, even assuming this can work (I haven't checked), it would be a lot more complicated than necessary for this result.

You write "what if $v$ is non-regular?" But this doesn't make sense: the concept of regularity applies to a language, not a word. For a given $u$, what language does $v$ have to belong to, in order for $uv$ to be in $L_2$?

If that's not enough of a hint, try reasoning with regular expressions. If $L_1$ is regular, then there is a regular expression that characterizes it. How can you use this regular expression to characterize $L_2$?

Best Answer from StackOverflow

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