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

\newcommand{\halfnfa}{\mbox{{\sc Half-Paths-NFA}}}

\head{CSG714}{Theory of Computation}{Spring 2008}{18 January 2008}{3}

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

{\bf Languages about integers}

Consider the collection of languages given by sets of nonnegative
integers.  That is, consider the collection $\{L : L \subseteq Z\}$,
where $Z$ is the set of nonnegative integers.  Thus, for instance, the
set of all primes, the set of all even numbers, the set of all sums of
squares, etc., are in this collection.
\begin{itemize}
\item[{\bf (a)}]
Show that the above collection of languages can be viewed as a
collection of languages over a single-element alphabet.  

({\em Remark:} This is an easy observation.)

\item[{\bf (b)}]
Prove that any context-free language over a single-element alphabet is
also a regular language.  

({\em Remark:} Note that together with part (a), this implies that any
set of integers recognized by a push-down automaton can also be
recognized by a finite state automaton.)
\end{itemize}

\end{document}
