Let Aibjck J K Show Context Free Q37136726

Let A = {aibjck | i > j >k}. Show that A is not context-free.

Solution

Assuming the question says {aibjck | i > j > k}

Solution:

Wewill prove this by contradiction.

Let’sassume that the language A is context free, so, pumping Lemma musthold for A.

Let s= a(n+2)b(n+1)cn sincei>j>k, here, i = n+2, j = n+1, k = n; It can be seen that |s|>= n, we must express s as  uvwxy such that |vwx|<= n, |vx| >= 1. Since, |vwx| <= n, uvwxy can be expressedin five ways:

vwx is ap for some p<=n, p>=1

vwx is ap bq

OR

 

OR