exercise 2.30

a.

Use the pumping lemma to show that the following language is not context free:
L = {0ⁿ1ⁿ0ⁿ1ⁿ| 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 uvⁱxyⁱz. 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 0^p1^p0^p1^p, 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 = {0ⁿ#0²ⁿ#0³ⁿ| 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 uvⁱxyⁱz. 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 0^p#0^2p#0^3p, 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 uvⁱxyⁱz. 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 a^pb^p#a^pb^p, 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 = {t₁#t₂# · · · #t_k| k ≥ 2, each t_i ∈ {a, b}*, and t_i = t_j 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 uvⁱxyⁱz. 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 q^p₁#q^p₂# · · · #q^p_k 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...]