\documentclass[12pt]{article}

\usepackage{tikz}
\usetikzlibrary{automata,positioning,arrows}
\newcommand{\lf}{\left\lfloor}
\newcommand{\rf}{\right\rfloor}
\newcommand{\lc}{\left\lceil}
\newcommand{\rc}{\right\rceil}
\newcommand{\Ceil}[1]{\left\lceil {#1}\right\rceil}
\newcommand{\ceil}[1]{\left\lceil {#1}\right\rceil}
\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\newcommand{\N}{{\sf N}}
\newcommand{\goes}{\rightarrow}
\newcommand{\st}{\mathrel{:}}
\newcommand{\nth}{n^{th}}

\newcommand{\es}{\emptyset}

\begin{document}

\newif{\ifshowsoln}
\showsolntrue % comment out to NOT show solution inside \ifshowsoln and \fi blocks.

\centerline{\bf Homework 6 DUE March 31 at 11:00 AM (No Dead Cat Extension)}

\centerline{\bf THIS HOMEWORK IS TWO PAGES LONG!!!!!!!!!!!!!!!}


\begin{enumerate}

\item(0 points, but if you actually miss the midterm without telling Dr. Gasarch ahead of time, you will lose 100 points on this homework)
When will the midterm be (give date and time)?
When will the final be (give date and time)?
By when do you have to tell Dr.\ Gasarch that
you cannot make the midterm? 

% For reference:
% Midterm is on Tuesday, March 31, in class
% Final is on Thursday, May 14, 8AM - 10AM
% Must tell Bill by Feb 11 in both cases


\item
(40 points)
For each of the following say if it is

\begin{itemize}
\item
REGULAR (in this case give a DFA or NFA or REGEX for it)
\item
CONTEXT FREE BUT NOT REGULAR (in this case give a CFG for it and prove it's not regular)
\item
NOT CONTEXT FREE (in this case just say NOT a CFL, no proof required).
\end{itemize}

Here are the languages:

\begin{enumerate}
\item
$\{a^{2n} b^{3n} \st n\in\N \}$.
\item
$\{a^{n^2+2n} \st n\in\N \}$.
\item
$\{a^{n+m} \st n, m \in \N \wedge n\ge 3m\}$
\item
$\{a^n b^n \st n \in \N \wedge n\le 100 \}.$
\end{enumerate}

\item
(20 points).
Give a CFG in Chomsky Normal Form for the languages. Try to make the the number of
productions as small as possible. 

\begin{enumerate}
\item
$L = \{ a^{16} \}$
\item
$L = \{ a^{17} \}$
\item
$L = \{ a^{28} \}$
\end{enumerate}


\textbf{GO TO NEXT PAGE FOR REST OF HOMEWORK}
\newpage
\item
(30 points)
For any $F \subseteq \N$, let $BILL(F)$ be the following set of strings.
$$BILL(F) = \{a^{n}b^{n} \st n \in F\}$$
\begin{enumerate}
\item
TRUE or FALSE. If $F$ is finite, then $BILL(F)$ is regular. If TRUE
then show how to, given a finite $F$, construct a DFA for $BILL(F)$.
\textbf{Give a reasonable upper bound on the number of states in the DFA as a function of $F$}
e.g. the number of states is the largest Fibonacci prime in $F$ (this is not the answer).
If FALSE, then give a finite set $F$ for which $BILL(F)$ is not regular and
prove that it is not regular.
\item
TRUE or FALSE. If $F$ is finite, then $BILL(F)$ is context free. If TRUE
then show how to, given a finite $F$, construct a CFG for $BILL(F)$.
\textbf{How many production rules does the CFG have as a function of F?}
e.g. the number of production rules is the largest Ramanujan prime in $F$ (this is not the answer).
(The CFG NEED NOT be in Chomsky Normal Form.)
If FALSE, then give a finite set $F$ for which $BILL(F)$ is not context free and
prove that it is not context free.
\item
TRUE or FALSE. If $F$ is infinite, then $BILL(F)$ is regular. If TRUE
then show how to, given a infinite $F$, construct a DFA for $BILL(F)$.
\textbf{How many states does the DFA have as a function of $F$}
e.g. the number of states is the smallest Ramanujan prime in $F$ (this is not the answer).
If FALSE, then give a infinite set $F$ for which $BILL(F)$ is not regular and
prove that it is not regular.
\item
TRUE or FALSE. If $F$ is infinite, then $BILL(F)$ is context free. If TRUE
then show how to, given a infinite $F$, how to construct a CFG for $BILL(F)$.
\textbf{How many production rules does the CFG have as a function of F?}
e.g. the number of states is the smallest Fermat prime in $F$ (this is not the answer).
(The CFG NEED NOT be in Chomsky Normal Form.)
If FALSE, then give a infinite set $F$ for which $BILL(F)$ is not context free. NO need
to prove it.
\end{enumerate}


\end{enumerate}

\end{document}