1
$\begingroup$

Show that the following languages are not regular in two ways: first by using closure properties then by using the Pumping lemma:

$$\text{(1) L1} = {a^n b^k c^{n+k} : n >= 0; k >= 0}$$

$$\text{(2) L2} = {a^n b^k : n \ne k}$$

So far for

  1. What I tried: Assume that L is regular. By P.L, there exists a P such that $w = a^pb^pc^{2p}$ there is $w_i = xy^iz , \mid y \mid \ge 1 , \mid xy \mid \le p $. We can imply $y = a^k$ and assuming k = 1 $w_0 = xy^0z = xz = a^{p-1}b^pc^{2p}$ which is not an element in L. Therefore there a contradiction and it is not regular. I don't know what to do for the closure properties
  2. Assume that L is regular. By P.L, there exists a P such that $w = a^pb^p$ from here im lost since it says $n \ne k$ for 2) can we say that $ w \notin L $ since $n = p = k$ thus it is a contradiction?
$\endgroup$
  • 1
    $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – D.W. Apr 8 '16 at 5:13
  • 1
    $\begingroup$ Your question is a very basic one. Let me direct you towards our reference questions which cover some fundamentals you seem to be missing in detail. Please work through the related questions listed there, try to solve your problem again and edit to include your attempts along with the specific problems you encountered. Good luck! $\endgroup$ – Raphael Apr 8 '16 at 6:46
2
$\begingroup$

For these hints, I'm assuming that you know (and are allowed to use) the fact that $\{a^nb^n\mid n\ge 0\}$ is not regular.

For (1), if $L_1$ was regular, then since regular languages are closed under intersection, we'd have $L_1\cap b^*c^*$ was regular. What's that language?

For (2), if $L_2$ was regular, then since regular languages are closed under complementation, we'd have $\overline{L_2}$ was regular, and so $\overline{L_2}\cap a^*b^*$ was regular. What's that language?

$\endgroup$

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.