2
$\begingroup$

How can i show that the following long language is not context free using the pumping lemma?

$L=\left\{abc^{i_1}bc^{i_2}...bc^{i_{2m}}def^{j_1}ef^{j_2}..ef^{j_{2n}}ghq^{k_1}hq^{k_2}...hq^{k_o}\right\}$

Such that:

$m,n,o \geq 1;$

$m>n>o>0;$

$i_1,i_2,...,i_{2m} \geq 0;$

$j_1,j_2,...,j_{2n} \geq 0;$

$k_1,k_2,...,k_o \geq 0$

And how can I conclude from that $L=\left\{0^i1^j2^k|1\le \:i<j<k\right\}$ is not a context free language?

I have been struggling with it for many hours, would really appreciate an explanation I can follow and learn from. The examples given in class are simpler and not on that level, and I don't know which z to take and how to break it in order to deduct in a proof that L is not context free.

Could you please give a slow explanation so I could learn fast?

My attempt for the first part:

Proving by negation that L is not a context free language: Assuming L is a context free language, then there should exist a pumping length P for which any string S such that $|S| \leq P$ can be divided into 5 pieces(uvxyz) while obeying the pumping lemma rules. Because of the information on the question, I'll focus on the first part of the lemma, i.e: $\forall i: uv^ixy^iz \in L$. The structure of a typical word from L will be:$S=abc^{p_1}bc^{p_2}...bc^{2p_i+2}def^{p_1}ef^{p_2}...ef^{2p_i}ghq^{p_1}...ghq^{2p_i-1}$. vxy cannot contain c,f,q's, We'll divide it into the following cases based on vxy. Don't know how to divide it or how to continue, would really appreciate your assistance with it. Very important to me

My attempt for the second part(I don't understand it well enough to solve the first part, I will ask for your help with it):

Proving by negation that L is not a context free language: Assuming L is a context free language, then there should exist a pumping length P for which any string S such that $|S| \leq P$ can be divided into 5 pieces(uvxyz) while obeying the pumping lemma rules. Because of the information on the question, I'll focus on the first part of the lemma, i.e: $\forall i: uv^ixy^iz \in L$. The structure of a typical word from L will be:$S=0^p1^p2^p$. vxy cannot contain a,b,c's, We'll divide it into the following cases based on vxy:

  1. Doesn't contain 0: pumping S with 0 to obtain $uv^0xy^0z=uxz$. in this case, there are fewer 1 or 2, so not in L.
  2. There's 0 but not 2: pumping S with 2 to obtain $uv^2xy^2z$, meaning more 0's than 2's, so it is not in L.
  3. There are no 2's: pumping S with 2 to obtain $uv^2xy^2z$, meaning more 1's or 0's than 2's, so it is not in L.

Since each option was checked and each one contradicted, It can be safe to assume that $L=\left\{0^i1^j2^k|1\le \:i<j<k\right\}$ is not a context free language since it does not adhere to the pumping lemma.

Thank you very much

$\endgroup$
  • $\begingroup$ Have you considered pumping a word like $abcbc\cdots bc$$defef\dots ef$$ghqhq\cdots hq$ where $c$ appears $2p+2$ times, $f$ $2p$ times and $q$ $2p-1$ times? $\endgroup$ – Apass.Jack Jun 27 at 19:56
  • $\begingroup$ can you please explain/ elaborate? $\endgroup$ – Auto Jun 27 at 20:00
  • $\begingroup$ I tried to write my attempt for this, but I am stuck on how to choose string s and divide it into 5 pieces to prove.I am quite sure that the property I should be using to show given language is not a context free one, is this property: $uv^ixy^iz \in L$. i don't understand it enough to solve by my own, that's why I asked to see how it's solved with explanation so I can adapt it to such complicated cases that are not $L=a^ib^i$ $\endgroup$ – Auto Jun 27 at 21:30
  • $\begingroup$ @Apass.Jack: Added my attempt for the second part, could you help me with the first, the more complicated one? $\endgroup$ – Auto Jun 27 at 21:59
  • $\begingroup$ The more complicated one is only slightly more complicated. Try pumping that word, observing the number of times $c$, $f$, or $q$ appears. $\endgroup$ – Apass.Jack Jun 28 at 0:17
2
$\begingroup$

Start with a long enough string $w$ in $L$ in which $m=p+2,n=p+1,o=p$ and

  • $i_1,...,i_{2m}=0$
  • $j_1,...,j_{2n}=0$
  • $k_1,...,k_{o}=0$

$w = a\; b^{2(p+2)}\; d\; e^{2(p+1)}\; g\; h^{p} $

Then apply pumping lemma (it should be easier ;-).

If you want to "reduce" $L$ to $L' = \left\{0^i1^j2^k|1\le \:i<j<k\right\}$ then you must use closure properties, in particular CFLs are:

  1. closed under homomorphism
  2. closed under reverse homomorphism
  3. closed under reversal

The homomorphism that you can use is: $H(a) = H(c) = H(d) = H(f) = H(g) = H(q) = \epsilon, H(b) = \bar{2}, H(e) = \bar{1}, H(h) = \bar{0}$

Applying $H$ to the language gives $H(L) = \{ \bar{2}^{2m} \bar{1}^{2n} \bar{0}^{o} \mid m > n > o > 0\}$

Then you can use a reverse homomorphism $\varphi(2)=\bar{2}\bar{2}, \varphi(1)=\bar{1}\bar{1}, \varphi(0) = \bar{0}$ and you get:

$\varphi^{-1}( H(L)) = \{ 2^m 1^n 0^o \mid m>n>o>0 \}$

and finally apply closure under reversal:

$(\varphi^{-1}( H(L)))^R = \{ 0^o 1^n 2^m \mid 0<o<n<m \} = L'$

If $L$ is CF then by closure properties $(\varphi^{-1}( h(L)))^R = L'$ should be CF, which is not the case.

$\endgroup$
  • $\begingroup$ Funny enough, this is almost the exact thing i did in my other post regarding deducting that the second language($L=\left\{0^i1^j2^k|1\le \:i<j<k\right\}$) is not context free as a consequence of this language not being context free(cs.stackexchange.com/questions/111247/…) $\endgroup$ – Auto Jun 28 at 11:14
  • $\begingroup$ so basically there can only be 4 possibilities in the pumping lemma implementation? $\endgroup$ – Auto Jun 28 at 11:15
  • $\begingroup$ just a quick question: what is the mathematical reasoning, meaning why, we can denote w as $w = a\; b^{p+2}\; d\; e^{p+1}\; g\; h^{p}$? $\endgroup$ – Auto Jun 28 at 11:22
  • $\begingroup$ @Auto: I also explained how you can "reduce" your language to $L'=\left\{0^i1^j2^k|1\le \:i<j<k\right\}$ ... it is another way to prove that $L$ is not context-free using only closure properties. $\endgroup$ – Vor Jun 28 at 12:23
1
$\begingroup$

Let us check the first part, $L=\left\{abc^{i_1}bc^{i_2}...bc^{i_{2m}}def^{j_1}ef^{j_2}..ef^{j_{2n}}ghq^{k_1}hq^{k_2}...hq^{k_o}\right\}$ where $m>n>o>0$, $i_1,i_2,...,i_{2m} \geq 0$, $j_1,j_2,...,j_{2n} \geq 0$, $k_1,k_2,...,k_o \geq 0$. Note the "where" clause means $\#_b(w)$ and $\#_e(w)$ are even and $\#_b(w)>\#_e(w)>2\#_h(w)$.

Assume $L$ is context-free for the sake of contradiction. Then there is a $p\ge1$, the pumping length such that every word in $L$ of length no less than $p$ can be written as $uvxyz$ such that $|vxy| \le p$, $|vy| \ge 1$ and $uv^kxy^kz$ is also a word in $L$ for all nonnegative number $k$.

Consider $w=a{\underbrace{bb\cdots b}_{2(p+2)\text{ times}}}$$d\underbrace{ee\dots e}_{2(p+1)\text{ times}}$$g\underbrace{hh\cdots h}_{p\text{ times}}$, a word that is in $L$ but "almost not in $L$".

Decompose $w=uvxyz$ where $v$ and $y$ together is the pumpable part of the word. There are following cases of the pumpable part.

  • The pumpable part contains $a$, $d$, or $g$.

    One of the them will disappear if we pump down by letting $k=0$, i.e., $uv^0xy^0z=uxz$.

  • Otherwise, the pumpable part must contain at least one of $b,e,h$.

    • the pumpable part does not contains $h$. So it must contain either $b$ or $e$.

      Pumping down by letting $k=0$ will decrease either $\#_b(w)$ or $\#_e(w)$ without changing $\#_h(w)$.

    • Otherwise, the pumpable part contains $h$. Since $vxy$ is too short to contain both $b$ and $h$, the pumpable part cannot contain $b$.

      Pumping up by letting $k=2$ will increase $\#_h(w)$ without changing $\#_b(w)$.

In all cases, $uvxyz$ can be pumped into a word not in $L$. So $L$ does not behave as described by the pumping lemma, which invalidate our assumption that $L$ is context free.


Exercise. Show that $\left\{w\in \{a,b,c\}^*\mid \#_a(w)> \#_b(w)\text{ and }\#_a(w)> \#_c(w) \right\}$ is not a context-free language.

$\endgroup$
  • $\begingroup$ Thank you so much for this elaborate answer. Studying it slowly and carefully. $\endgroup$ – Auto Jun 28 at 12:18
  • $\begingroup$ Each of you gave me an extraordinary answer to a different question. Both of you answered my question and helped me a lot in learning, but I don't know to who I should give the "answer"(v).Is it possible to accept two answers here? $\endgroup$ – Auto Jun 28 at 14:03
  • $\begingroup$ @Auto There is no way to accept more than one answer. It is up to you to choose one. $\endgroup$ – Apass.Jack Jun 28 at 15:39

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.