Let Aibjck J K Use Pumping Lemma Context Free Languages Show Context Free Q37021022

Let A = {aibjck | i > j >k}. Use the pumping lemma for context-free languages to show that Ais not context-free.

Solution

Assuming the question says a^ib^jc^k (^ depicts power here)i>j>k;

Solution:

This is a proof by contradiction.

Let’s assume that the language A is context free, so, pumpingLemma must hold for A.

Let s = a^(n+2)b^(n+1)c^n since i>j>k, here, i = n+2, j =n+1, k = n; It can be seen that |s| >= n, we must express sas  uvwxy such that |vwx| <= n, |vx| >= 1. Since,|vwx| <= n, uvwxy can be expressed in five ways:

1. vwx is a^p for

OR

 

OR