\documentclass{article}

%
% title macros
%
\newcommand\myname{Prof. Nadeem Abdul Hamid}
\newcommand\course{CSC 320 Spring 2005}
\newcommand\hwnum{4}
\newcommand\duedate{Friday, March 4, 2005}

\newcommand\probtitle{
 \title{Homework \hwnum\ --\ Due: \duedate}\author{\myname\\\course}\date{}
 \maketitle}
\newcommand\solntitle{
	{\bf\flushright \myname\\\course\\\today\\Homework \hwnum\\}}


%
% local macros
%
\newcommand\powset[1]{\mathcal{P}(#1)}
\newcommand\problem{\section{}}



%
% main document
%
\begin{document}

\probtitle 

\problem
Answer problem 1.38 in the textbook (page 90).

\problem
\begin{itemize}
 \item Give a context-free grammar for the language of palindromes (over the alphabet $\mathtt{a}, \mathtt{b}$): $\{ w\,|\,w = w^\mathcal{R}$, that is, $w$ is a palindrome $\}$.
 
  \item Convert your CFG for the language of palindromes to a pushdown automaton (PDA) following the algorithm we discussed in class (page 108-109 in the textbook).
\end{itemize}


\problem
Show that the set of strings over the alphabet $\{ \mathtt{a}, \mathtt{b} \}$ with twice as many $\mathtt{a}$'s as $\mathtt{b}$'s is a context-free language. (That is, give a PDA or CFG that recognizes/generates the language.)




\end{document}