# exercise 2.30

### a.

Use the pumping lemma to show that the following language is not context free:
L = {0n1n0n1n| n ≥ 0}

We'll show that L is not a context free language using the pumping lemma. We suppose that L is CFL and we'll prove that we'll have contradictions in any case.

Since we supposed that L is a CFL, we can write the language in form of uvixyiz. The constraint are that i ≥ 0, and there are a number p (the "pumping length") where |vy|>0 and |vxy|≤p.

So, let we choose the string 0p1p0p1p, that is evidently more long than p. There are two cases:

1. v contains only 0s or 1s. In this case, pumping the string make a new string with a different number of 0s than 1s, and it's not recognized by L. Similar for y.
2. v contains both 0s and 1s. In this case pumping the string make a new string with perhaps the same number of 0s and 1s, but in disorder, so it's not recognized by L. Similar for y.

In any case we obtain a contradiction, so we proved that "L is a CFL" is false, then L is not a CFL. ☐

### b.

Use the pumping lemma to show that the following language is not context free:
L = {0n#02n#03n| n ≥ 0}

We'll show that L is not a context free language using the pumping lemma. We suppose that L is CFL and we'll prove that we'll have contradictions in any case.

Since we supposed that L is a CFL, we can write the language in form of uvixyiz. The constraint are that i ≥ 0, and there are a number p (the "pumping length") where |vy|>0 and |vxy|≤p.

So, let we choose the string 0p#02p#03p, that is evidently more long than p. There are two cases:

1. v contains a #. In this case, pumping the string make a new string with a uncorrect number of #, and it's not recognized by L. Similar for y.
2. v contains only 0s. In this case pumping the string make a new string with a number of 0 that doesn't respect the ratio 1:2:3, so it's not recognized by L. Similar for y.

In any case we obtain a contradiction, so we proved that "L is a CFL" is false, then L is not a CFL. ☐

### c.

Use the pumping lemma to show that the following language is not context free:
L = {w#t| w is a substring of t, where w, t ∈ {a, b}*}

We'll show that L is not a context free language using the pumping lemma. We suppose that L is CFL and we'll prove that we'll have contradictions in any case.

Since we supposed that L is a CFL, we can write the language in form of uvixyiz. The constraint are that i ≥ 0, and there are a number p (the "pumping length") where |vy|>0 and |vxy|≤p.

So, let we choose the string apbp#apbp, that is evidently more long than p. There are three cases:

1. v or y contain a #. In this case, pumping the string make a new string with a uncorrect number of #, and it's not recognized by L.
2. v or y are at the left part of the string. In this case, pumping up v or y we can obtain a string longer than the right part, that is not recognized by L.
3. v or y are at the right part of the string. In this case, pumping down v or y we can obtain a string shorter than the left part, that is not recognized by L.

### d.

Use the pumping lemma to show that the following language is not context free:
L = {t1#t2# · · · #tk| k ≥ 2, each ti ∈ {a, b}*, and ti = tj for some i ≠ j}

Use the pumping lemma to show that the following language is not context free:
L = {w#t| w is a substring of t, where w, t ∈ {a, b}*}

We'll show that L is not a context free language using the pumping lemma. We suppose that L is CFL and we'll prove that we'll have contradictions in any case.

Since we supposed that L is a CFL, we can write the language in form of uvixyiz. The constraint are that i ≥ 0, and there are a number p (the "pumping length") where |vy|>0 and |vxy|≤p.

So, let we choose the string qp1#qp2# · · · #qpk where k ≥ 2 and q is the string t = {0,1}* and the length of t is p, that is evidently more long than p. There are two cases:

1. v or y contain only #. In this case, pumping the string make a new string with a uncorrect number of #, and it's not recognized by L.

[to be continued...]