4
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ Yes you can use pumping lemma to prove that some languages ARE NOT regular. Whether it's useful here or not, depends on whether you can come up with one language that satisfy the condition. When u or v is not in L1, that's the same thing as saying the condition is L complement. However, what if u is not regular? That's going to hurt you. Your pumping lemma will show that it's going to be NOT regular. JFYI, there has been a conjecture that said for 2 non-regular, they are regular under many closure properties. But don't rely on that though. Only good for certain langs. Correct me if I am wrong. $\endgroup$
    – CppLearner
    Commented Apr 21, 2012 at 18:04
  • 6
    $\begingroup$ Hint: Prove that $L_3 = \{u v | u \in L_1\}$ is regular. $\endgroup$
    – sdcvvc
    Commented Apr 21, 2012 at 18:57

3 Answers 3

Reset to default
7
$\begingroup$

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$?

Improve this answer
$\endgroup$
1
  • $\begingroup$ "the concept of regularity applies to a word, not a language" That should be the other way around, I assume. $\endgroup$
    – sepp2k
    Commented Apr 21, 2012 at 22:28
6
$\begingroup$

Write $L_2$ as $$\{uv \mid u \in L_1, v\in \Sigma^*\} \cup \{uv \mid u\in \Sigma^*, v\in L_1\}$$ (convince yourself it is OK to do so)

Then check about right/left quotient. With that, the proof is trivial.

EDIT: actually, quotient is not needed. Only concatenation.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ You need an (easy) closure property of $\mathrm{REG}$, too. $\endgroup$
    – Raphael
    Commented Apr 22, 2012 at 12:09
5
$\begingroup$

There is another question about proving that languages are not regular. My personal favorite way to do it is, essentially, equivalent to the Myhill-Nerode Theorem.

For proving that a language is regular, you can either show it is expressible by a DFA, NFA, Regular Expression, etc. or you can use the fact that regular languages are closed under:

  • Intersection (easiest to show with DFAs)
  • Union (easy with regular expressions)
  • Reversal (easy with NFAs)
  • Taking prefixes, as in $L_3$ from @sdvvc's comment (easy with DFAs)
  • Suffixes (can be obtained from reversal and prefixes)

Some combinations of these should deal with the language in the question.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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