\documentclass[11pt]{amsart}

\usepackage{amsmath,amsthm,amssymb}
\usepackage{stmaryrd}

\usepackage{fancyhdr} % Allows customization of verbatim environments

\usepackage{xcolor}

%\usepackage[textheight=8.5in, margin=1.6in]{geometry}
\usepackage[
  hmarginratio={1:1},     % equal left and right margins
%  vmarginratio={1:1},     % equal top and bottom margins
  %textwidth=400pt,        % new text width
  heightrounded,          % always useful
  %bindingcorrection=5mm,  % binding correction
  total={6in,8in}
]{geometry}
\headheight=13pt
\footskip=13pt

\usepackage{needspace}  % <-- to prevent bad pagebreak over environment titles
% Use:  \Needspace{3\baselineskip} before opening an environment

\usepackage{graphicx}

% Tikz stuff.
\usepackage{tikz}
%\usepackage{tkz-graph}
\usepackage{pgfplots}
%\usepackage{tikz-3dplot}
\pgfplotsset{compat=newest}
%\usepgfplotslibrary{fillbetween}
%\usetikzlibrary{cd}
%\usetikzlibrary{positioning}
%\usetikzlibrary{decorations.pathmorphing}    
%\usetikzlibrary{decorations.pathreplacing}
%\usetikzlibrary{arrows.meta,calc}
%\usetikzlibrary{bending}
%\usetikzlibrary{decorations.markings,shapes.geometric}
%\tikzset{->-/.style={decoration={markings, mark=at position #1 with
%  {\arrow{>}}},postaction={decorate}}}
%\tikzset{-|-/.style={decoration={markings, mark=at position #1 with
%  {\arrow{stealth}}},postaction={decorate}}}
%\tikzset{movearrow/.style 2 args ={
%        decoration={markings,
%	  mark= at position {#1} with {\arrow{#2}} ,
%        },
%        postaction={decorate}
%    }
%}
%\tikzset{<--/.style={decoration={markings, mark=at position #1 with
%  {\arrow{<}}},postaction={decorate}}}
\tikzstyle{ball} = [circle,shading=ball, ball color=black,
    minimum size=1mm,inner sep=1.3pt]
%\tikzstyle{bball} = [circle,shading=ball, ball color=blue,
%    minimum size=1mm,inner sep=1.3pt]
%\tikzstyle{miniball} = [circle,shading=ball, ball color=black,
%    minimum size=1mm,inner sep=0.5pt]
%\tikzstyle{redminiball} = [circle,shading=ball, ball color=red,
%    minimum size=1mm,inner sep=0.5pt]
%\tikzstyle{mminiball} = [circle,shading=ball, ball color=black,
%    minimum size=0.6mm,inner sep=0.1pt]
%\tikzstyle{mycircle} = [draw,circle, minimum size=1mm,inner sep=1.3pt]
%\newcommand*{\DashedArrow}[1][]{\mathbin{\tikz [baseline=-0.25ex,-latex, dashed,#1] \draw [#1] (0pt,0.5ex) -- (1.3em,0.5ex);}}%

%%%% tikz style for finite automata
\usetikzlibrary{automata, positioning, arrows}
\tikzset{fa/.style={
    ->, % makes the edges directed
    >=stealth, % makes the arrow heads bold
    node distance=3cm, % specifies the minimum distance between two nodes. Change if necessary.
    every state/.style={thick, fill=gray!10}, % sets the properties for each ’state’ node
    initial text=$ $, % sets the text that appears on the start arrow
}}
%%%%

\usepackage{needspace}  % <-- to prevent bad pagebreak over environment titles
% Use:  \Needspace{3\baselineskip} before opening an environment

\usepackage[shortlabels]{enumitem}
\setlist[enumerate]{itemsep=4pt,leftmargin=*,label={(\alph*)}}
%\setlist[enumerate]{itemsep=2pt,label={\arabic*.}}

\usepackage[T1]{fontenc}
\renewcommand{\labelitemi}{\guillemotright}

\allowdisplaybreaks

\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\W}{\mathbb{W}}
\newcommand{\KK}{\Bbbk}
\newcommand{\ve}{\varepsilon}
\newcommand{\scribe}{
  \begin{center}%
    Scribe~$=$ \rule{7cm}{0.15mm}%
  \end{center}%
  \medskip%
}
\DeclareMathOperator{\im}{\mathrm{im}}
\DeclareMathOperator{\id}{\mathrm{id}}
\DeclareMathOperator{\glb}{\mathrm{glb}}
\DeclareMathOperator{\lub}{\mathrm{lub}}

\newcounter{problem}
\renewcommand \thesection {\theproblem}
\newenvironment{prob}[1][]
{
\refstepcounter{problem}\par\medskip
\def\myArg{#1}
  \ifx\myArg\empty
    \noindent \textsc{Problem~\theproblem.} \rmfamily
  \else
    \noindent \textsc{Problem~\theproblem\ (\textnormal{#1}).} \rmfamily
  \fi
}
{
\medskip

}

\parskip = 0.05in
\parindent = 0.0in

%\pagestyle{empty}
%\pagenumbering{gobble}

\fancypagestyle{firststyle}
{
\fancyhead[L,LO]{
\textit{\small Math 387 Group problems, Friday Week 1}
}
\renewcommand{\headrulewidth}{0pt}
}

\begin{document}
\thispagestyle{firststyle}

\begin{enumerate}[label=\arabic*.\ , ref=\arabic*]
  \item Find a regular expression for each of the following languages on
    $\{0,1\}$:
    \smallskip

    \begin{enumerate}
      \item Words not ending in~$11$.
      \item Words of even length, length at least~$3$ and with second letter equal to~$0$. 
    \end{enumerate}
    \smallskip

  \item  Let~$A$ be the following DFA:
    \begin{center}
      \begin{tikzpicture}[fa,baseline={([yshift=-1em] current bounding box.north)}]
	\node[state, initial, accepting] (q1) {$q_{1}$};
	\node[state, right of=q1] (q2) {$q_{2}$};
	\node[state, accepting, right of=q2] (q3) {$q_{3}$};
	\draw (q1) edge[loop above,above] node{$0$} (q2);
	\draw (q1) edge[above] node{$1$} (q2);
	\draw (q2) edge[loop above,above] node{$0$} (q2);
	\draw (q2) edge[above, bend left] node{$1$} (q3);
	\draw (q3) edge[loop above,above] node{$0$} (q3);
	\draw (q3) edge[above, bend left] node{$1$} (q2);
      \end{tikzpicture}
    \end{center}
    \begin{enumerate}
      \item Convert $A$ into an NFA having (i) an initial states with no
	transitions leading into it, and (ii) a single accept state having no
	transitions of it.  The resulting NFA should have five states, including
	the initial state~$q_{0}$ and the unique accepting state~$q_{4}$.
      \item Rip out state $q_{1}$, and draw the resulting GNFA.  The transitions
	will be labeled with regular expressions.
      \item Recall the general prescription for ripping out a state given in the text:
	\begin{center}
	  \begin{tikzpicture}[fa,baseline={([yshift=-1em] current bounding box.north)}]
	    \node[state] (i) {$q_{i}$};
	    \node[state, right of=i] (j) {$q_{j}$};
	    \node[state] at (1.5,-2) (rip) {$q_{\mathrm{rip}}$};
	    \draw (i) edge[above, bend left] node{$R_{4}$} (j);
	    \draw (i) edge[left, bend right] node{$R_{1}$} (rip);
	    \draw (rip) edge[loop below,below] node{$R_{2}$} (rip);
	    \draw (rip) edge[right, bend right] node{$R_{3}$} (j);
	    \node at (1.5,-4) {before};
	    \begin{scope}[xshift=6cm]
	      \node[state] (i) {$q_{i}$};
	      \node[state, right of=i,xshift=1.5cm] (j) {$q_{j}$};
	      \draw (i) edge[above] node{$(R_{1})(R_{2})^{*}R_{3}\cup R_{4}$} (j);
	      \node at (1.5,-4) {after};
	    \end{scope}
	  \end{tikzpicture}
	\end{center}
	\smallskip
	
	Letting~$q_{i}=q_{0}$, $q_{j}=q_{3}$, and $q_{\mathrm{rip}}=q_{2}$,
	identify $R_{1}, R_{2}, R_{3}$ and $R_{4}$.  What regular expression
	labels the transition from~$q_{0}$ to $q_{3}$ after ripping out~$q_{2}$?
	What obvious simplification can you make involving the empty set?
      \item Similarly, letting~$q_{i}=q_{3}$, $q_{j}=q_{3}$, and $q_{\mathrm{rip}}=q_{2}$,
	identify $R_{1}, R_{2}, R_{3}$ and $R_{4}$.  What regular expression
	labels the transition from~$q_{3}$ to $q_{3}$ after ripping out~$q_{2}$?
      \item Rip out $q_{2}$ and draw the resulting GNFA
      \item Rip out $q_{3}$ to produce a GNFA with two states.
      \item What is the resulting regular expression for the language accepted
	by~$A$?
      \item Give a simple description of $L(A)$ in words.
    \end{enumerate}
  \item Negate the DFA from Problem the previous problem by exchanging accept and reject
    states to create the DFA $A^{c}$.
    \begin{enumerate}
      \item What is $L(A^{c})$, in words.
      \item Convert $A^{c}$ into an NFA having (i) an initial states with no
	transitions leading into it, and (ii) a single accept state having no
	transitions of it.  The resulting NFA should have five states, including
	the initial state~$q_{0}$ and the unique accepting state~$q_{4}$.
      \item Rip out~$q_{1}$.
      \item The resulting GNFA has states $q_{0},q_{2},q_{3},q_{4}$.  Recall the
	general prescription for ripping out a state given in the text:
	\begin{center}
	  \begin{tikzpicture}[fa,baseline={([yshift=-1em] current bounding box.north)}]
	    \node[state] (i) {$q_{i}$};
	    \node[state, right of=i] (j) {$q_{j}$};
	    \node[state] at (1.5,-2) (rip) {$q_{\mathrm{rip}}$};
	    \draw (i) edge[above, bend left] node{$R_{4}$} (j);
	    \draw (i) edge[left, bend right] node{$R_{1}$} (rip);
	    \draw (rip) edge[loop below,below] node{$R_{2}$} (rip);
	    \draw (rip) edge[right, bend right] node{$R_{3}$} (j);
	    \node at (1.5,-4) {before};
	    \begin{scope}[xshift=6cm]
	      \node[state] (i) {$q_{i}$};
	      \node[state, right of=i,xshift=1.5cm] (j) {$q_{j}$};
	      \draw (i) edge[above] node{$(R_{1})(R_{2})^{*}R_{3}\cup R_{4}$} (j);
	      \node at (1.5,-4) {after};
	    \end{scope}
	  \end{tikzpicture}
	\end{center}
	Letting~$q_{i}=q_{2}$, $q_{j}=q_{4}$, and $q_{\mathrm{rip}}=q_{3}$,
	identify $R_{1}, R_{2}, R_{3}$ and $R_{4}$.  What regular expression
	labels the transition from~$q_{2}$ to $q_{4}$ after ripping out~$q_{3}$?
	How does that regular expression simplify?
      \item Rip out~$q_{3}$.
      \item Rip out~$q_{2}$.
      \item What is the resulting regular expression for $L(B)=L(A^{c})$.
    \end{enumerate}
  \item (Bonus) The text describes a method for converting an NFA with $n$ states into a
    DFA with $2^{n}$ states. Show that this bound is roughly tight.
    Specifically, show that for every~$n$ there exists a language that can be
    recognized with an $(n+1)$-state NFA but cannot be recognized by a DFA with
    fewer than~$2^{n}$ states.
\end{enumerate}
\end{document}
