Peter Linz Edition 5 Exercise 8.1 Question 7(c) (Page No. 212)

Question

Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free.

                                                                     $L = \{a^nb^jc^k:k=jn\}$.

Answer 1

We need 2stacks to establish the relationship between a,b,c and k,j,n ...so not possible in CFL.

 

For ex, 

j=2, n=3 $\Rightarrow$ k=6

We get string “aaabbcccccc”  ..Its corresponding PDA-stack is:

 

c

c

c

c

c

c

b

b

a

a

a

Z

Clearly it requires 2stack, hence not in CFL.

Answer 2

The language L = {a^nb^jc^k : k = jn } can be shown to not be context-free by using the pumping lemma for context-free languages.

The pumping lemma states that if a language L is context-free, then there exists a number p (the pumping length) such that any string s in L of length greater than or equal to p can be divided into three substrings x, y, and z such that:

1. |xy| <= p
2. |y| > 0
3. for all i >= 0, xy^i z is in L

If we take any string from L that follows the pattern a^nb^jc^k, the pumping lemma tells us that we can pump the middle substring y any number of times to get a new string still in L.

For example, let's take the string "a^2b^2c^2"

If we divide this string into x = "a", y = "a" and z = "b^2c^2", we can pump y any number of times to get a^2b^2c^2, a^3b^2c^2, a^4b^2c^2, ...

However, we can see that in all of these new strings the value of k is not equal to j*n. Which means that this string can't be in the language L.

Therefore, we can conclude that the language L = {a^nb^jc^k : k = jn } is not context-free.