0
$\begingroup$

i'm trying to figure out whether this Union $\left [ L_1=\{a^lb^mc^m|l,m\ge 0\} \cup L(b^*c^*)\right]=K$ is regular or not, now since regular languages are closed under intersection, so i assume $K$ is regular then its intersection with $L(a^*b^*)$ should be regular which is $K\cap L(a^*b^*)=L(a^*)\cup L(b^*)$ right ?

1 - Does this implies that the Union is also regular ?

2 - i know that $L=\{a^lb^mc^m|l,m\ge1\}$ is CFL, but is $L_1$ also CFL ?, which is basically $L_1=L\cup \{\epsilon ,a,bc\}$

3 - is $K$ regular or not and how to prove it ?

Any Hints would be appreciated.

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ I can't comprehend your question. You are aware that $\cup$ is union, not intersection, right? And that the "left" half of $L_1$ is not regular? $\endgroup$ – Raphael♦ Dec 20 '17 at 11:13
  • $\begingroup$ @Raphael i actually meant the intersection of the Union with $L(a^*b^*)$ $\endgroup$ – proless8 Dec 20 '17 at 11:22
  • $\begingroup$ The fact that the intersection of $K$ with a regular language is a regular language, doesn't tell you anything about $K$. $L_1$ is indeed not regular - you can't pump $b^pc^p$, $p$ being the pumping length. $\endgroup$ – potestasity Dec 20 '17 at 11:32
  • $\begingroup$ @potestasity That word can be pumped perfectly fine. Use $ab^pc^p$. That said, the OP seems to be looking for a proof using closure properties. $\endgroup$ – Raphael♦ Dec 20 '17 at 12:22
  • $\begingroup$ @Raphael I'm not sure I understand. $ab^pc^p$ can be pumped (by choosing $\epsilon$, $a$ and $b^pc^p$ as the three parts), but I fail to see how you can pump $b^pc^p$. $\endgroup$ – potestasity Dec 20 '17 at 13:08
0
$\begingroup$

You are not starting with the right proof idea. It's this:

  1. I want to show $L$ is not regular.
  2. Assume towards a contradiction that $L$ is regular.
  3. Since REG is closed against $f$, I conclude that $L' = f(L)$ is also regular.
  4. But I already know that $L'$ is not regular (from elsewhere). Contradiction; $L$ can't be regular.

See here for complete examples.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ thanks i understand the proof idea, so i will use the complement of $K$ to get i think this language $L=\{a^nb^nc^n\}$, but i can't get the complement of $L_1$ any idea ? $\endgroup$ – proless8 Dec 20 '17 at 14:15
  • 1
    $\begingroup$ @proless8 The complement of $L_1$ does not have a lot of structure, so that's unlikely to help. Hint: Try to isolate $b^mc^m$ which you should know to be non-regular (up to homomorphism). $\endgroup$ – Raphael♦ Dec 20 '17 at 15:53

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.