\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{\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 4 Morally Due Mar 3 at 11:00 AM}

\centerline{\bf THIS HOMEWORK IS THREE 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{\bf GOTO NEXT PAGE FOR MORE HOMEWORK}

\newpage

\item
(30 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 it's not regular.
You may use the Extended Pumping Lemma and closure properties.

Recall that $\#_a(w)$ is the number of $a$'s in $w$.
For this problem and forever, $\N = \{0, 1, 2, ...\}$.

\begin{enumerate}
\item
(8 points)
(Alphabet is $\{a\}$.)
$$\{a^n a^{2n} \st n\in \N\}$$
\item
(8 points)
(Alphabet is $\{a,b\}$.)
Here, \(x^R\) denotes the reverse of a string (so $(aab)^R = baa$).
$$\{w \st w \neq w^R\}$$
\item
(7 points)
(Alphabet is $\{a\}$.)
$$\{a^{\ceil{\sqrt{n}}} \st n\in \N\}$$
\item
(7 points)
(Alphabet is $\{a,b\}$.)
$$\{w \st \#_a(w) \ge 10 \cdot \#_b(w)\}$$
\item
(0 points, think about)
(Alphabet is $\{a\}$.)
$$\{a^{\ceil{n\log(n)}} \st n\in \N\}$$
\end{enumerate}

\centerline{\bf GOTO NEXT PAGE FOR MORE HOMEWORK}
\newpage

\item
(30 points) The alphabet for the following parts is $\{a\}$.
\begin{enumerate}
\item
(8 points) Give a DFA for $$L = \{ a^n \st n \equiv 0 \pmod{2019} \}$$ Draw a diagram. You can use "...". Try to make it
have as few states as possible. How many states does your DFA have?
\item
(0 points, think about as it may be on the midterm) Is there a DFA in part (a) that has fewer states than yours?
\item
(8 points) Give a DFA for $$L = \{ a^n \st n \not \equiv 0 \pmod{2019} \}$$ Draw a diagram. You can use "...". Try to make it
have as few states as possible. How many states does your DFA have?
\item
(0 points, think about as it may be on the midterm) Is there a DFA in part (c) that has fewer states than yours?
\item
(7 points)  Give an NFA for $$L = \{ a^n \st n \equiv 0 \pmod{2019} \}$$ Draw a diagram. You can use "...". 
Try to make it have fewer states than the DFA. You may fail. How many states does your NFA have?
\item
(0 points, think about as it may be on the midterm) Is there a NFA in part (e) that has fewer states than yours?
\item 
(7 points) Give an NFA for $$L = \{ a^n \st n \not \equiv 0 \pmod{2019} \}$$ with fewer states. Draw a diagram. 
You can use "...". Try to make it have fewer states than the DFA. You may fail.How many states does your NFA have?
\item
(0 points, think about as it may be on the midterm) Is there a NFA in part (g) that has fewer states than yours?
\end{enumerate}


\end{enumerate}
\end{document}