\documentclass[11pt]{article}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{epsfig}
\usepackage{graphics}

\textheight= 8in \textwidth=5.5in
\parindent =0pt
\hsize = 4in
%\voffset = 1 in
%\hoffset= 1 in
\parindent = 0pt
\parskip = 0.2cm
\tolerance = 10000 \textheight= 8in \textwidth=4.5in
\parindent =0pt
\hsize = 4in
%\voffset = 1 in
%\hoffset= 1 in
\parindent = 0pt
\parskip = 0.2cm
\tolerance = 10000
\input{../../../../papers/newcomm}

\begin{document}
\bibliographystyle{plain}



{\bf  Intro Theory CS}  \hfill \today \hrule
{\bf G. Farin }\\




\centerline{\bf Homework \# 2}

\centerline {\it due: midnight {\bf2/28} by email to TAs.}

\centerline{\em No handwritten homework!} \vspace{3cm}

{\bf 1.} Figure \ref{fig:DFA1} shows a DFA. Give a regular expression for the
language it accepts.

 \bef
    \epsfig{file=DFA1.ps, height = 2 in}
    \caption{A DFA.}
   \label{fig:DFA1}
\eef


{\bf 2.} Let a regular language be given by the regular expression ${\bf
a}^*\bb^+({\bf a}\bb)^*$. Attach a JFLAP file with an equivalent DFA.

{\bf 3.}Let a CFG be given by
\begin{eqnarray*}
    S & \rightarrow aT | a \\
    T & \rightarrow bS | b
\end{eqnarray*}
Describe the structure of the language generated by this CFG.

{\bf 4.} Let
    $$
        L=\{ a^{k+n} b^k c^{k+m}; n,m,k \ge 0 \}.
    $$
Find a CFG for $L$.


\end{document}
