\documentclass[11pt]{article}
\usepackage{handout2e}
\begin{document}
\input{macros}
\input{courseMacros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\head{CSG714}{Theory of Computation}{Spring 2009}{16 January 2009}{4}

\begin{center}
\Large{\bf Problem of the Week -- 2}
\end{center}

\noindent {\bf Minimizing number of states and stack alphabet size}

Consider the collection of all context-free languages over the
alphabet $\{0,1\}$.
\begin{itemize}
\item
Determine the smallest integer $s$, if it exists, such that for every
context-free language $L$ there exists a PDA that accepts $L$ and has
alphabet size at most $s$?

\item
Determine the smallest integer $s$, if it exists, such that for every
context-free language $L$ there exists a PDA that accepts $L$ and has
at most $s$ states?
\end{itemize}

Justify your answers.
\end{document}