\documentclass[12pt]{article}
\usepackage{fancyhdr}
\newcommand{\N}{{\sf N}}
\newcommand{\into}{{\rightarrow}}
\newcommand{\goes}{{\rightarrow}}
\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{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\newcommand{\e}{\varepsilon}
\newcommand{\st}{\mathrel{:}}
\newcommand{\4}{\\\\}
\newcommand{\printn}{\textbf{Print your name neatly here:}}
\usepackage{amsmath}
\pagestyle{fancy}
\lhead{\printn}
\begin{document}
  \centerline{\bf CMSC452 Midterm}

  \noindent
  {\large
  \thispagestyle{myheadings}

  \begin{enumerate}

    \addtolength{\itemsep}{-2mm}  % reduced space between lines

    \item This  is  an open-everything exam. You can use anything except ask another person. Caution: if you copy from
the web or elsewhere mindlessly you will probably get it wrong.

    \item  There are 4 problems which add up to 100 points.  
    The exam is 3 hours.

    \item For each question show all of your work and {\bf use LaTeX or write VERY NEATLY}.
{\bf Clearly indicate} your answers.  No credit for illegible answers. {\bf Write your name on every page where indicated.}

    \item Please write out the following statement:
          {\it I pledge on my honor that I
          will not give or receive any unauthorized assistance on this
          examination\/}.   
\end{enumerate}

\bigskip
\bigskip
\bigskip
\bigskip
\bigskip

\medskip

\noindent
{\bf Fill in the following:}

\[
\begin{array}{rl}
{\rm NAME: } & \cr
{\rm SIGNATURE: } & \cr
{\rm UID: } & \cr
\end{array}
\]

\newpage

\newif{\ifshowsoln}

\showsolntrue

\begin{enumerate}

\item
(30 points)
For each of the following languages say if it's 
\begin{itemize}
    \item REGULAR
    \item CONTEXT FREE and NOT REGULAR
    \item NOT CONTEXT FREE
\end{itemize}

\centerline{
\textbf{NO PROOF REQUIRED!}
}

You will get 6 points for a right answer and lose 4 points for a wrong answer. 
However, your score cannot go under 0 (e.g. if you answer
only one question and it's incorrect, you will have a 0, not a -4.).
You do not need to prove your result. \\
DO NOT GUESS!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

The alphabet is $\{a,b\}$ and $\N = \{0,1,2,\ldots\}$.

\begin{enumerate}
\item
$L_1 = \{ a^{n^2} \st n \in \N, n > 1000 \}$
\item
$L_2= \{a^n b^{2n} \st n \in \N \}$
\item
$L_3 = \{a^n b^m \st n,m \in \N, n \le m^2 \}$
\item
$L_4= \{w \st \#_a(w) = \#_b(w)\}$
\item
$L_5 = \{a^{n^2} \st n \in \N, n \le 1000\}$
\end{enumerate}


\newpage

\item
(20 points)
Let  $\Sigma=\{a,b\}$ and let $L$ be regular via DFA $M = (Q,\Sigma,\delta,s,F)$.
Construct an NFA for $L^*$.

\noindent
(NOTE - we are asking for a construction, not a 
drawing. Recall we did constructions with DFAs to prove
that if $L_1$ and $L_2$ are regular then so
are BLAH.)

\newpage
\item
(20 points)
For this problem you may use the following theorem.

\noindent
{\bf Theorem.} If $x$ and $y$ are relatively prime then
\begin{itemize}
\item
For all $z\ge xy-x-y+1$ there exist $c,d\in\N$ such that $z=cx+dy$.
\item
There is no $c,d\in\N$ such that $xy-x-y=cx+dy$.
\end{itemize}

The alphabet is $\{a\}$.
Let

$$L = \{ a^n : n\ne 50 \}$$

\begin{enumerate}
\item
(10 points)
Does there exist a DFA for $L$ with less than 55 states?
If so then draw the DFA; you may use DOT DOT DOT (You DO NOT have to prove that the DFA works.)
If not then PROVE there is no such DFA.

\item
(10 points)
Does there exist an NFA for $L$ with less than 40 states?
If so then draw the NFA; you may use DOT DOT DOT (You DO NOT have to prove that the NFA works.)
If not then PROVE there is no such NFA.
\end{enumerate}

\textbf{You may answer this problem on this page and the next page.}

\newpage

\hbox{\ }

\newpage
\item
(30 points)
Let $L = \{a^n \st n \equiv 4 \pmod {32}\}$.
\begin{enumerate}
    \item (15 points) Draw a DFA that recognizes $L$ with 32 states. You may use DOT DOT DOT.
    \item (15 points) Present a CFG in Chomsky Normal Form that generates $L$ and uses $\le 16$ production rules.
Explain why your CFG generates $L$.
\end{enumerate}

\textbf{You may answer this problem on this page and the next page.}

\vfill

\eject

\hbox{\ }

\vfill

\eject

\end{enumerate}


\newpage

\centerline{Scratch Paper}

\end{document}