CMSC 28000 — Lecture 18

Since $L$ is context-free, there must be a CFG $G$ in Chomsky normal form that generates it. Let $m$ be the number of variables in $G$. Then the pumping length for $L$ will be $n = 2^m$.

Consider a word $w \in L$ with $|w| \geq n = 2^m$. Let $T$ be a parse tree for $w$ and fix it. We saw from a problem set problem that there must be a path in $T$ from the root to a leaf with at least $m+1$ internal nodes.

Pick a longest such path. Since there are at least $m+1$ internal nodes along this path and only $m$ variables, there must be a variable that appears twice in the path. Suppose this variable is $X$ and we have that there must be an occurrence of $X$ that is closest to the leaf on our chosen path.

Let $T_1$ and $T_2$ be two subtrees of $T$ that are rooted at the two occurrences of $X$ on the path closest to the leaf. Let $T_2$ be the tree rooted at the closest occurrence of $X$ so $T_2$ must be a proper subtree of $T_1$. Furthermore, every path from the root of $T_1$ to a leaf has at most $m+1$ internal nodes and therefore $T_1$ has at most $2^m = n$ leaf nodes.

Let $x$ be the word for which $T_2$ is the parse tree rooted at $X$ and let $v$ and $y$ be the words formed by the leaves of the parse tree $T_1$ rooted at $X$ around $T_2$ such that $T_1$ is a parse tree for the word $vxy$. Then we let $u$ and $z$ be the words formed by the leaves of $T$ around $T_1$ such that $T$ is a parse tree for the word $w = uvxyz$.

Now we need to show that $uvxyz$ is a factorization for $w$ such that the conditions of the pumping lemma hold. First, to see that $|vxy| \leq n$, we just observe that $T_1$ can have at most $2^m = n$ leaf nodes.

Next, to see that $vy \neq \varepsilon$, we note that since both $T_1$ and $T_2$ are rooted at $X$, we can construct a parse tree in which $T_1$ is removed and replaced by $T_2$. This would then be a parse tree for $uxz$. However, recall that every parse tree for a word in a grammar in CNF must have exactly the same size. Since $T_2$ was already shown to be smaller than $T_1$ we must have that $uxz \neq uvxyz$ and therefore $vy \neq \varepsilon$.

Finally, to see that $uv^ixy^iz \in L$ for all $i \in \mathbb N$, we first note that we have already shown $uv^0 xy^0 z \in L$ above. To see that this holds for $i > 1$, we can perform a similar substitution by replacing $T_2$ with $T_1$ to give us a parse tree for $uv^2xy^2$. We can then repeat this process any number of times to obtain a parse tree for $uv^ixy^iz$.

Suppose that $L$ is context-free and let $n$ be the pumping length for $L$. Let $w = a^n b^n c^n$. Clearly, $w \in L$ and $|w| = 3n \geq n$. Now, we must consider all factorizations of $w = uvxyz$ such that $|vxy| \leq n$ and $vy \neq \varepsilon$. There are two cases to consider.

1. $vxy = a^s b^t$ such that $0 < s+t \leq n$ and $vy \neq \varepsilon$. Observe that since $|vxy| \leq n$, it cannot contain any $c$'s. Therefore, choosing $i > 1$, we have that either $|uv^ixy^iz|_a > |uv^ixy^iz|_c$ or $|uv^ixy^iz|_b > |uv^ixy^iz|_c$ and thus $uv^ixy^iz \not \in L$. By the same argument, we can choose $vxy = b^s c^t$ and arrive at the fact that either $|uv^ixy^i|_b > |uv^ixy^iz|_a$ or $|uv^ixy^iz|_c > |uv^ixy^iz|_a$.
2. $vxy = b^s$ such that $0 < s \leq n$ and $vy \neq \varepsilon$. Again, choosing $i > 1$, we have that $|uv^ixy^iz|_b > |uv^ixy^iz|_c$ and thus $uv^ixy^iz \not \in L$. An analogous argument holds for $vxy = a^s$ and $vxy = c^s$.

Thus, every factorization of $w = uvxyz$ fails to satisfy the pumping lemma and therefore $L$ is not context-free as assumed.

Suppose $L$ is context-free and let $n$ be the pumping length for $L$. Let $w = a^n b^n a^n b^n$. Then $w = (a^n b^n)^2 \in L$ and $|w| = 4n \geq n$. Now, we must consider factorizations $w = uvxyz$ with $|vxy| \leq n$ and $vy \neq \varepsilon$. There are two cases.

1. $vxy$ lies entirely in either the first or second half of $w$. There are three sub-cases to deal with here. Since $|vxy| \leq n$, it can contain either all $a$'s, all $b$'s, or some factor $a^j b^k$. In any of these cases, if $vxy$ lies in the first half of $w$, we have $uv^ixy^iz = a^{n+(i-1)\cdot s} b^{n +(i-1) \cdot t} a^n b^n$ for some $s,t \geq 0$ and for all $i \geq 2$. Then $uv^ixy^iz \not \in L$ since it is not a square. The same argument can be applied to the case when $vxy$ is entirely in the second half of $w$.
2. $vxy$ straddles both halves of $w$. In this situation, one can observe that since $|vxy| \leq n$, if we take $i > 1$, then $uv^ixy^iz = a^n b^{n+(i-1)\cdot j} a^{n+(i-1) \cdot k} b^n$ for some $j,k > 0$. Clearly, $w$ is not a square and thus $w \not \in L$.

Thus, every factorization of $w = uvxyz$ fails to satisfy the pumping lemma and therefore $L$ is not context-free as assumed.

Suppose $L$ is a context-free language. Then it is closed under intersection with regular languages. However, consider the regular language $L(a^* b^* c^*)$ and $$L \cap L(a^* b^* c^*) = \{a^m b^m c^m \mid m \in \mathbb N \}.$$ This language is known to be not context-free. Therefore $L$ must not be context-free.

Let $L_1 = \{a^i b^i c^j \mid i,j \geq 0\}$ and let $L_2 = \{a^i b^j c^j \mid i,j \geq 0\}$. It is easy to see that $L_1$ and $L_2$ are both context-free. Consider for $\sigma_1, \sigma_2 \in \Sigma$ the languages \begin{align*} L_{\sigma_1,\sigma_2} = \{\sigma_1^m \sigma_2^m \mid m \geq 0 \}, \\ K_{\sigma_1} = \{\sigma_1^i \mid i \geq 0\}. \end{align*} We have already seen that $L_{\sigma_1,\sigma_2}$ is context-free and $K_{\sigma_1}$ is just $\sigma_1^*$, which is regular (and therefore, context-free). Since context-free languages are closed under concatenation, we have $L_1 = L_{a,b} K_c$ and $L_2 = K_a L_{b,c}$. Thus, $L_1$ and $L_2$ are context-free languages. Then, we have $$L_1 \cap L_2 = \{a^i b^i c^i \mid i \geq 0\}.$$ We have already shown that this language is not context-free.

Let $L_1 = \{ a^i b^j c^k \mid i \neq j\} \cup \{a^i b^j c^k \mid j \neq k\}$ and let $L_2 = \overline{L(a^* b^* c^*})$. It is clear that $L_2$ is regular. To see that $L_1$ is context-free, we observe that we can write $$\{a^i b^j c^k \mid i \neq j\} = \left(\{ a^i b^j \mid i < j\} \cup \{a^i b^j \mid i > j\} \right) \{c^k \mid k \geq 0\}$$ and similarly, we have $$\{a^i b^j c^k \mid j \neq k\} = \{a^i \mid i \geq 0\} \left(\{ b^j c^k \mid j < k\} \cup \{b^j c^k \mid j > k\} \right).$$

Then $L = L_1 \cup L_2$ is a context-free language. However, observe that by DeMorgan's laws, we have $$\overline L = \overline{L_1 \cup L_2} = \overline{L_1} \cap \overline{L_2}.$$ First, we observe that $\overline L_2 = L(a^* b^* c^*)$ and therefore words of $\overline L$ must be of this form. Next, we recall that $\overline{L_1}$ consists of words that are not of the form $a^i b^j c^k$ with $i \neq j$ or $j \neq k$. In other words, if words of $L_1$ are of the form $a^i b^j c^k$, we must have $i = j = k$. But this means that $$\overline L = \overline{L_1} \cap \overline{L_2} = \{a^m b^m c^m \mid m \geq 0\}.$$ Of course, we have already seen that this language is not context-free.