\documentclass[11pt]{article}
\textheight 9.25in
\textwidth 6.6in
\parskip=\medskipamount
\parindent=0.2in
\oddsidemargin -.1in
\evensidemargin -.1in
\topmargin -.4in
\headsep 0in
\topsep 0in
\itemsep 3ex

\newcommand{\blank}{\mbox{\_\_\_\_\_\_\_\_\_\_\_\_}}
\newcommand{\rma}{{\rm a}}
\newcommand{\rmb}{{\rm b}}
\newcommand{\rmma}{{\rm\bf a}}
\newcommand{\rmmb}{{\rm\bf b}}
\newcommand{\set}[1]{\{\,#1\,\}}
\newcommand{\mdot}{\!\cdot\!}
\newcommand{\AND}{\; \wedge \;}
\newcommand{\OR}{\; \vee \;}
\newcommand{\intersect}{\cap}
\newcommand{\implies}{\Longrightarrow}
\newcommand{\symmdiff}{\bigtriangleup}

\begin{document}
\sloppy
\pagestyle{empty}
\noindent
{\Large\bf
\begin{tabular*}{\textwidth}
{@{}l@{\extracolsep{\fill}}c@{\extracolsep{\fill}}r@{}}
CSE396, Spr'19 & First Prelim Exam & Mar.\ 12, 2019
\end{tabular*}
}


\noindent
Closed books and laptops, one notes sheet allowed, closed neighbors, 75 minutes.
Do {\sc all four} problems 
{\bf on these exam sheets}.
Please {\em show all your work\/}---this may help for
partial credit.
The exam totals 80 pts., subdivided as shown.

{\bf Notation:} 
All problems on this exam use alphabet
$\Sigma = \set{a,b}$.
$\#c(x)$ stands for the number of occurrences of the 
character $c$ in the string $x$.  
% The symmetric difference of two languages $A$ and $B$
% is defined by $A \symmdiff B = (A \setminus B) \cup (B \setminus A)$,
% where $\setminus$ is difference of sets.



\bigskip
\bigskip
\noindent
{\bf (1) (20 pts.)}

Let $A = \set{x \in \set{a,b}^*: bb \mbox{~is a substring of $x$
and $\#a(x)$ is even}}$.
Design a deterministic finite automaton (DFA) $M$ such that
$L(M) = A$.
A node-arc diagram that shows the start
and final states clearly is good enough---you
need not write out tables or ``$M = (Q,\Sigma,\delta,s,F)\dots$'' etc.
For full credit, you must either have comments explaining a design
strategy that makes the correctness of your $M$ clear,
or you must use theorems to build $M$ from smaller machines.
Trial-and-error may take too long.




% \bigskip
% \bigskip
\newpage
\noindent
{\bf (2) (15 + 12 = 27 pts.)}

Let $N$ be the NFA defined by
$N = (Q,\Sigma,\delta,s,F)$ with $Q = \set{1,2,3}$,
$\Sigma = \set{a,b}$, $s = 1$, $F = \set{2}$, and $\delta$
given by the arcs $(1,b,2)$, $(1,\epsilon,2)$, $(1,a,3)$,
$(2,b,3)$, $(3,b,1)$, and $(3,a,2)$ as shown in the following
node-arc diagram:
\vspace{0.6in}


\begin{itemize}
\item[(a)]
Calculate a DFA $M$ such that $L(M) = L(N)$.  
% (Here no ``comments'' are needed if you apply theory clearly.)
\item[(b)]
Calculate a regular expression $r$ such that $L(N) = L(r)$.
\end{itemize}

\newpage
% \bigskip
% \bigskip
% \vspace{2in}
\noindent
{\bf (3) (5 $\times$ 3 = 15 pts.)} {\em True/False\/}.

Please write out the words
{\tt true} and/or {\tt false} in full.
No justifications are needed.
%
\begin{itemize}
\item[(a)]
If $A^* = A$, then the language $A$ includes the empty string.
\item[(b)]
If $A$ and $B$ are regular languages recognized by 3-state DFAs, then
$A \cap B$ can be recognized by a 6-state DFA.
\item[(c)]
The empty relation on a nonempty set is transitive.
\item[(d)]
The intersection of two non-regular languages is always non-regular.
\item[(e)]
If there is a string $w$ such that no string $x$ in a regular language
$A$ has $w$ as a substring, then every DFA $M$ such that
$L(M) = A$ has a dead state.
\end{itemize}

\bigskip
\begin{verbatim}
 (a) __________   (b) __________   (c) __________   (d) __________   (e) __________
\end{verbatim}




% \bigskip
% \bigskip
\newpage
\noindent
{\bf (4) (18 pts.)}

Define $L = \{x \in \{a,b\}^*: |x|$ is even and there is a $b$ in the
left half of $x\}$.
For instance, $ba$, $aabaaa$, and $baaaaa$ belong
to $L$, but $\epsilon$, $ab$, and $baaaa$ do not---the last fails because
its length is odd.  
Prove using the Myhill-Nerode technique that $L$ is not a regular language.






% \medskip
% \centerline{\sc End of Exam.}
\end{document}


