\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{\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 5 Morally Due Mar 5}

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

\begin{enumerate}
\item
(40 points)
\begin{enumerate}
\item
(0 points)
READ the $R(i,j,k)$ method (on the course webpage under notes)
for GIVEN a DFA, produce a REGEX for the same language.
NOTE that it is a DYNAMIC PROGRAMMING algorithm.
(That means it's a recursion, but done from the bottom up instead of top down.)
\item
(20 points)
Write the $R(i,j,k)$ algorithm as a RECURSIVE program.
\item
(0 points)
READ up on Memoization (there is a nice Wikipedia entry on it,
plus it is in many algorithms texts and on the web in other places).
\item
(20 points)
Write the $R(i,j,k)$ algorithm as a MEMOIZATION program which has
the benefits of both recursion and dynamic programming!
\end{enumerate}


\centerline{GO TO NEXT PAGE!!!!!!!!!!!}

\newpage

\item
(40 points)
For each of the following state if it's REGULAR or NOT REGULAR.
If it's REGULAR then give a DFA or REGEX for it.
If it's NOT REGULAR then prove that.

Recall that $n_a(w)$ is the Number of $a$'s in $w$.
Also, recall that $\N$ (natural numbers) denotes the set of \emph{nonnegative} integers.

\begin{enumerate}
\item
(8 points)
(Alphabet is $\{a\}$.)
$$\{ a^n a^n \mid n\in  \N \}$$
\item
(8 points)
(Alphabet is $\{a,b\}$.)
Here, \(x^R\) denotes the reverse of a string (so $(aab)^R = baa$).
$$\{ xyx^R \mid x,y\in \{a,b\}^* \}$$
\item
(8 points)
(Alphabet is $\{a\}$.)
$$\{ a^{\ceil{\log_2(n+1)}} \mid n\in \N\}$$
\item
(8 points)
(Alphabet is $\{a,b\}$.)
$$\{ a^{n^2} b^{n} \mid n\in \N\}$$
\item
(8 points)
(Alphabet is $\{a,b\}$.)
$$\{ a^{m} b^n \mid m,n\in \N\hbox{ AND } m\ge n^2 \}$$
\end{enumerate}

\item
(20 points)
(NOTE- this is similar to HW03, Problem 3 which was harder than I intended.
Hence we will revise those grades as follows:

Grade on HW03, Problem 3 = 

$$\max\{\hbox{(Grade HW3, Prob 3), (Grade HW 5, Prob 3-- This problem)} \}$$

And NOW onto the problem:

Let
$$L = \{ a^n \mid n\not\equiv 0 \pmod{3811} \}.$$
\begin{enumerate}
\item
(10 points) Prove that ANY DFA for $L$ has to have $\ge 3811$ states.
\item
(10 ponts) Prove or Disprove: There is an NFA for $L$ with $<3811$ states.
\end{enumerate}

\end{enumerate}
\end{document}