exercise 2.2

Posted by On Filed under Calcolabilità e linguaggi formali

a. Theorem

Use the languages A = {ambncn| m, n ≥ 0} and B = {anbncm| m, n ≥ 0}
together with Example 2.36 to show that the class of context-free languages
is not closed under intersection.

a. Proof

The intersection of two languages is when a string is recognized both by the first and the second. If a string w is recognized by A, this means that it has the same number of bs and cs; if the string w is recognized by B, this means that it has the same number of as and bs. If w is recognized by the intersection of the two languages, this means that it has the same number of bs and cs and the same number of as and bs, so m = n and the number of as, bs and cs is the same.

A ∩ B = {anbncn| n ≥ 0}

This is exactly the language of the example 2.36.

Lemma: C = {anbncn| n ≥ 0} that isn't context-free.

We can assume that C = {anbncn| n ≥ 0} is context-free to obtain a contradiction.

Let p the pumping length for C that is guarranteed to exist by the pumping lemma. Select the string s = apbpcp. Clearly, s is a member of C and s is not shorter than p.

The pumping lemma states that s can be pumped, but we show that it cannot. In other words, we show that no matter how we divide s into uvxyz, one of the three conditions of the lemma is violated.

    1. for each i ≥ 0, uvixyiz ∈ A
    2. |vy| > 0
    3. |vxy| ≤ p

the condition 2. affirms that v and y are nonempty. We consider one of two cases, depending on whether substring v and y contains the same symbol or not.

  1. If v contains the same symbol, v must contain only as or bs or cs, and the same holds for y. So pumping up the string, we don't have the same number of as, bs and cs yet. This is a violation of the first condition.
  2. If v and y contains more than one symbol, pumping up uvixyiz can bring to the same number of as, bs, and cs, but the order will be uncorrect. Again, this is a violation of the first condition.

In both cases we obtain a contradiction, so we can say that CFLs are not closed under intersection. ☐

b. Theorem

Use part (a) and DeMorgan’s law (Theorem 0.20) to show that the class of context-free languages is not closed under complementation.

b. Proof

If CFL were closed under complementation, A is CFL ⇔ ¬A is CFL and B is CFL ⇔ ¬B is CFL. But ¬A ∩ ¬B is not a CFL, as proved before.

Using the DeMorgan's law, that says

¬A ∩ ¬B = ¬(A ∪ B)

we can say that ¬(A ∪ B) is not a CFL, even if A ∪ B is it (see exercice 2.16).

So, we can say that CFLs are not closed under complementation. ☐