22  More Exercises

% noend hides “end for”; drop it to keep them

Exercise 22.1 Show that \{\textcolor{darkred}{\mathtt{a}}^n\textcolor{darkred}{\mathtt{b}}^n\textcolor{darkred}{\mathtt{c}}^n :n\in \mathbb{N}\}\in \mathbf{co}\mathbf{CFL}. (Recall the definition of a \mathbf{co} class from Section 4.3 Equation 4.1.)

Exercise 22.2 Show that \{w\textcolor{darkred}{\mathtt{\#}}w :w\in \{\textcolor{darkred}{\mathtt{a}},\textcolor{darkred}{\mathtt{b}}\}^*\}\in \mathbf{co}\mathbf{CFL}.

Exercise 22.3 Given an algorithm that on input a context-free grammar G decides whether

1. \mathscr{L}(G)=\emptyset.
2. \mathscr{L}(G)\in \mathbf{Finite}.

What is the cost of your algorithm as a function of the number of symbols in G?