\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

\usepackage{tikz}

\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
{\bf Name and St.ID\#:}\blank\blank\blank\blank\blank\blank\blank\blank 

\bigskip
\noindent
{\Large\bf
\begin{tabular*}{\textwidth}
{@{}l@{\extracolsep{\fill}}c@{\extracolsep{\fill}}r@{}}
CSE396, Spr'17 & First Prelim Exam & Mar.\ 14, 2017
\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}.  Extra sheet(s) may be requested later.
Please {\em show all your work\/}---this may help for
partial credit.
The exam totals 100 pts., subdivided as shown.

{\bf Notation:} 
Given any two (possibly equal) states $p,q$ in a DFA, NFA, or GNFA
$N = (Q,\Sigma,\delta,s,F)$,
$L_{p,q}$ denotes the language of strings that $N$ can process from
state $p$ to state $q$.  So $L(N) = \cup_{q \in F} L_{s,q}$.
Besides
$\#c(x)$ standing for the number of occurrences of the 
character $c$ in the string $x$, we write
$\#u(x)$ for the
number of times $u$ occurs as a substring of $x$.
As on Problem Set 4, this counts occurrences that overlap.
% 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) (6 + 18 + 24 pts.)}

% Define $A$ to be the language of strings $x \in \{a,b\}^*$ such that
% $x$ either begins with $aa$ or ends with $bb$, but not both.  
% Design a 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.
% %
% ({\em Important time-saver:\/} Design $M$ by theory and/or
% strategy---trial-and-error may take too long.  The correctness of
% your $M$ must be clear either from your theoretical technique or
% from strategic comments on how $M$ works.)

Let $A$ be the language of strings $x$ over alphabet $\set{a,b}$ such that:
\begin{itemize}
\item
$x$ begins with `$a$' and ends with `$a$'
\item
between every two `$a$'s in $x$ there are at least two `$b$'s.
\end{itemize}
For example, the string $abba$ belongs to $A$, but $ababa$ does not.

\begin{itemize}
\item[(a)]
For each of the following strings, say whether it belongs to $A$:

\bigskip
\centerline{(i)~$\epsilon$ \qquad (ii)~$a$ \qquad (iii)~$abbaa$}

\item[(b)]
Design a 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.
%
({\em Important time-saver:\/} Design $M$ by theory and/or
strategy---trial-and-error may take too long.  The correctness of
your $M$ must be clear either from your theoretical technique or
from strategic comments on how $M$ works.)

%\item[(c)]
% {\sc Your Choice:} {\em Either\/} write a regular expression
% $\alpha$ such that $L(\alpha) = A$, {\em xor\/} write an NFA $N$
% such that $L(N) = A$.  (A DFA where you don't bother showing a dead state
% and arcs to it counts as an NFA.)
\end{itemize}


\noindent
{\bf (2) (18 + 18 = 36 pts.)}

Consider the following NFA $N$.  (It has $Q = \set{1,2,3}$, start state
$s = 1$, $F = \set{1}$ making the start state the only final state, and arcs
$\delta=\set{(1,a,1),(1,b,3),(2,a,1),(2,b,2),(2,\epsilon,3),(3,a,2),(3,b,1)}$.)

\begin{center}
\begin{tikzpicture}[scale=0.2]
\tikzstyle{every node}+=[inner sep=0pt]
\draw [black] (45.7,-23.2) circle (3);
\draw (45.7,-23.2) node {$1$};
\draw [black] (45.7,-23.2) circle (2.4);
\draw [black] (29.7,-35.4) circle (3);
\draw (29.7,-35.4) node {$3$};
\draw [black] (49.2,-41.6) circle (3);
\draw (49.2,-41.6) node {$2$};
\draw [black] (32.665,-35.857) arc (79.7248:64.99921:56.708);
\fill [black] (46.52,-40.26) -- (46,-39.47) -- (45.58,-40.38);
\draw (40.55,-37.07) node [above] {$a$};
\draw [black] (46.666,-20.372) arc (188.86424:-99.13576:2.25);
\draw (51.01,-16.96) node [right] {$a$};
\fill [black] (48.53,-22.25) -- (49.4,-22.62) -- (49.25,-21.63);
\draw [black] (47.564,-25.546) arc (33.5139:-11.97392:17.361);
\fill [black] (47.56,-25.55) -- (47.59,-26.49) -- (48.42,-25.94);
\draw (50.87,-31.6) node [right] {$a$};
\draw [black] (46.288,-42.305) arc (-81.3518:-133.92419:17.318);
\fill [black] (31.67,-37.66) -- (31.9,-38.57) -- (32.59,-37.85);
\draw (37.64,-42.23) node [below] {$\epsilon$};
\draw [black] (43.678,-25.416) arc (-44.16641:-61.18255:48.051);
\fill [black] (32.37,-34.04) -- (33.31,-34.09) -- (32.83,-33.21);
\draw (39.35,-30.64) node [below] {$b$};
\draw [black] (51.273,-39.448) arc (163.79888:-124.20112:2.25);
\draw (56.31,-38.54) node [right] {$b$};
\fill [black] (52.17,-41.94) -- (52.8,-42.64) -- (53.08,-41.68);
\draw [black] (31.121,-32.761) arc (147.62461:107.02643:21.128);
\fill [black] (42.78,-23.87) -- (41.87,-23.63) -- (42.16,-24.58);
\draw (35.15,-26.78) node [above] {$b$};
\draw [black] (40.4,-17.8) -- (43.6,-21.06);
\draw (38.16,-17.32) node [above] {$start$};
\fill [black] (43.6,-21.06) -- (43.4,-20.14) -- (42.68,-20.84);
\end{tikzpicture}
\end{center}

%\vspace{2in}
\begin{itemize}
\item[(a)]
Convert $N$ into a DFA $M$ such that $L(M) = L(N)$.
\item[(b)]
Write a regular expression for $L(N)$.
\end{itemize}




\newpage
\noindent
{\bf (1) (5 $\times$ 3 + 1 = 16 pts.)} {\em True/False\/}.

Please write out the words
{\tt true} and/or {\tt false} in full.
No justifications are needed.
{\em Be sure to write your answers in the exam books.\/}
The last one is worth 4 pts., not 3.

\begin{itemize}
\item[(a)]
It is possible to have regular languages $A$ and $B$ such that
$A \cap B$ is not regular.
\item[(b)]
Every subset of a regular language is a regular language.
\item[(c)]
For all languages $A$ (even non-regular ones),
$A\mdot A^* \cup \set{\epsilon} = A^*$.
\item[(d)]
If $N$ is an NFA with $k$ states, then there is always a DFA $M$ with
at most $3k$ states such that $L(M) = L(N)$.
\item[(e)]
For any two states $p,q$ in a DFA $M$, there is a regular expression
$\alpha$ that matches precisely those strings that $M$ can process from
state $p$ to $q$---i.e., such that $L(\alpha) = L_{pq}$.
\end{itemize}


% \bigskip
% \bigskip
% \noindent
% {\bf (4) (7 pts.)}
% 
% Let $L = \{x \in \Sigma^*:$ both of the substrings $aa$ and $bb$ occur in $x$,
% each at least once$\}$.
% Write a regular expression $r$ such that $L(r) = L$.
% (Hint: Break into two cases, one for $aa$ coming first, the other for
% $bb$ coming first.)



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

Over $\Sigma = \{0,1\}$, define $L = \set{x: \#00(x) = \#01(x)}$.
Prove via the Myhill-Nerode technique that $L$ is not a regular
language.  




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


