LEC TOC 7

CFLs are closed under unions, concatenation, and kleene star, homo, inv homo, CF subs. Not closed under intersection and complement.

Write a grammar for $\{a^n{b}^n{c}^n{\}}^c$.

$$\begin{array}{r}\{a^{\ast }{b}^{\ast }{c}^{\ast }{\}}^c\cup \{a^{n_1}{b}^{n_2}{c}^{n_3}|n_1\ne n_2\}\cup \{a^{n_1}{b}^{n_2}{c}^{n_3}|n_2\ne n_3\}\cup \{a^{n_1}{b}^{n_2}{c}^{n_3}|n_3\ne n_1\}\end{array}$$

You can further split $\{a^{n_1}{b}^{n_2}{c}^{n_3}|n_1\ne n_2\}$ as $\{a^{n_1}{b}^{n_2}{c}^{n_3}|n_1<n_2\}\cup \{a^{n_1}{b}^{n_2}{c}^{n_3}|n_1>n_2\}$.