Indice dei contenuti

### a.

Use the pumping lemma to show that the following language is not context free:

*L* = {0* ^{n}*1

*0*

^{n}*1*

^{n}*|*

^{n}*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 ^{i}xy^{i}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}*1

*0*

^{p}*1*

^{p}*, that is evidently more long than*

^{p}*p*. There are two cases:

*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*.*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^{n}#0^{2n}#0^{3n}| 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 ^{i}xy^{i}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

*#0*

^{2p}*, that is evidently more long than*

^{3p}*p*. There are two cases:

*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*.*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 ^{i}xy^{i}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 ^{p}b^{p}*#

*a*, that is evidently more long than

^{p}b^{p}*p*. There are three cases:

*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.*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.*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_{1}#t_{2}# · · · #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}*}

*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.

*L* is a CFL, we can write the language in form of *uv ^{i}xy^{i}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}_{1}#q^{p}_{2}# · · · #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:

*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...]