1
$\begingroup$

For my homework assignment, I have to come up with a non-cfl that is pumpable. I came up with the following: $$ C = \{a^n b^n c^n d^m \mid n \ge 1 \text{ and } m \ge 1 \} $$

I'm not sure whether this works. For the pumping lemma, let $p$ being the pumping length. If I generate a string with $p$ $a$'s, $b$'s, and $c$'s, and only one $d$, my only choice for $vxy$ would be $d$. Pumping this down to $v^0xy^0$ gives $a^p b^p c^p$, thus escaping the language. However, if I let $m$ be greater than or equal to zero, if I choose a string with no $d$'s, then I am forced to put either $a$'s, $b$'s or $c$'s in my $vxy$ string.

$\endgroup$
7
  • 3
    $\begingroup$ See Example of a non-context free language that nonetheless CAN be pumped? for some examples. $\endgroup$ Oct 12, 2013 at 22:36
  • $\begingroup$ I don't get the examples there; they seem a little too complex lol. this is a homework problem, and i have to proof that it's not a cfl by arguing my way through, so i'd like to keep the language simple. $\endgroup$
    – Yuen Hsi
    Oct 12, 2013 at 23:50
  • $\begingroup$ @YuenHsi: If it's homework, you should do it by yourself. $\endgroup$
    – Raphael
    Oct 13, 2013 at 12:53
  • $\begingroup$ @Raphael If that is the spirit of this site, then you should close the question. $\endgroup$ Oct 13, 2013 at 20:20
  • $\begingroup$ @Raphael So did you get in University of Kaiserslautern and become a PhD student without ever asking for help for any homework assignments? $\endgroup$
    – Yuen Hsi
    Oct 13, 2013 at 20:28

1 Answer 1

0
$\begingroup$

As you say "thus escaping the language" which means your example language is not pumpable: for $m=1$ we cannot pump $d$ and stay in the language. Instead consider $D= C \cup \{a,b,c\}^*$. Now we can pump $d$ whenever it is present, and we can pump any string that does not contain $d$.

$\endgroup$
1
  • $\begingroup$ Hey, thanks for your response; I thought of doing that but I didn't know how to proof that D is not context free. Even though C isn't a CFL, I thought CFL languages are not closed under union? {a, b, c}* is regular, isn't it? $\endgroup$
    – Yuen Hsi
    Oct 13, 2013 at 20:29

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