\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

}

\newenvironment{sol}
{\emph{Solution.}
}
{
  \medskip

}


\parskip = 0.05in
\parindent = 0.0in

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

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

\begin{document}
\thispagestyle{firststyle}

\begin{enumerate}[label=\arabic*.\ , ref=\arabic*]
  \item Create an NFA using three states recognizing the language consisting of
    all words on $\Sigma=\{0,1\}$ ending in $01$.

    \begin{sol}
      \begin{tikzpicture}[fa,baseline={([yshift=-1em] current bounding box.north)}]
	\node[state, initial] (q1) {};
	\node[state, right of=q1] (q2) {};
	\node[state, accepting, right of=q2] (q3) {};
	\draw (q1) edge[loop above] node{$0,1$} (q1);
	\draw (q1) edge[above] node{$0$} (q2);
	\draw (q2) edge[above] node{$1$} (q3);
      \end{tikzpicture}
    \end{sol}
  \item Create an NFA using three states recognizing the language $0^{*}1^{*}0^{+}$.  

    \begin{sol}
      \begin{tikzpicture}[fa,baseline={([yshift=-1em] current bounding box.north)}]
	\node[state, initial] (q1) {};
	\node[state, right of=q1] (q2) {};
	\node[state, accepting, below of=q2] (q3) {};
	\draw (q1) edge[loop above] node{$0$} (q1);
	\draw (q1) edge[above] node{$1$} (q2);
	\draw (q1) edge[left] node{$0$} (q3);
	\draw (q2) edge[loop above] node{$1$} (q2);
	\draw (q2) edge[right] node{$0$} (q3);
      \end{tikzpicture}
    \end{sol}
  \item\label{01wed:3} Consider the NFA
    \begin{tikzpicture}[fa,baseline={([yshift=-1em] current bounding box.north)}]
      \node[state, initial] (q1) {$q_1$};
      \node[state, right of=q1] (q2) {$q_{2}$};
      \node[state, right of=q2] (q3) {$q_3$};
      \node[state, accepting, right of=q3] (q4) {$q_4$};
      \draw (q1) edge[loop above] node{$a$} (q1);
      \draw (q1) edge[above, bend left] node{$a$} (q2);
      \draw (q2) edge[above, bend left] node{$b$} (q1);
      \draw (q2) edge[above] node{$b$} (q3);
      \draw (q3) edge[above] node{$a$,$\varepsilon$} (q4);
    \end{tikzpicture}
    \bigskip

    \begin{enumerate}
      \item Is $abab$ accepted?  Explain.
      \item What is $\delta(q_{2},b)$?
    \end{enumerate}
    \medskip

    \begin{sol}
      \begin{enumerate}
	\item The word $abab$ is accepted by the following path:
	  \[
	    q_{1}\xrightarrow{a}q_{2}\xrightarrow{b}q_{1}\xrightarrow{a}q_{2}\xrightarrow{b}q_{3}\xrightarrow{\varepsilon}q_{4}.
	  \]
	\item $\delta(q_{2},b)=\{q_{1},q_{3},q_{4}\}$.
      \end{enumerate}
    \end{sol}
  \item Create an NFA for the regular expression $(01\cup 011)^{*}$ using the
    ideas presented in today's lecture: (i) find NFAs for $01$ and for $011$,
    (ii) combine them to get an NFA for $01\cup 011$, and (iii) modify the NFA
    just constructed to find an NFA for $(01\cup 011)^{*}$.
    \medskip
    \begin{sol}
      First, create NFAs for $01$ and $011$: 
      \bigskip

      \begin{tikzpicture}[fa,baseline={([yshift=-1em] current bounding box.north)}]
	\node at (-2,0) {$01$:};
	\node[state, initial] (q1) {};
	\node[state, right of=q1] (q2) {};
	\node[state, accepting, right of=q2] (q3) {};
	\draw (q1) edge[above] node{$0$} (q2);
	\draw (q2) edge[above] node{$1$} (q3);
      \end{tikzpicture}
      \bigskip

      \begin{tikzpicture}[fa,baseline={([yshift=-1em] current bounding box.north)}]
	\node at (-2,0) {$01$:};
	\node[state, initial] (q1) {};
	\node[state, right of=q1] (q2) {};
	\node[state, right of=q2] (q3) {};
	\node[state, accepting, right of=q3] (q4) {};
	\draw (q1) edge[above] node{$0$} (q2);
	\draw (q2) edge[above] node{$1$} (q3);
	\draw (q3) edge[above] node{$1$} (q4);
      \end{tikzpicture}
      \bigskip

      \begin{tikzpicture}[fa,baseline={([yshift=-1em] current bounding box.north)}]
	\node at (-3,0) {$01\cup 011$:};
	\node[state, initial] (ii) {};
	\node[state, above right of=ii] (p1) {};
	\node[state, right of=p1] (p2) {};
	\node[state, accepting, right of=p2] (p3) {};
	\node[state, below right of=ii] (q1) {};
	\node[state, right of=q1] (q2) {};
	\node[state, right of=q2] (q3) {};
	\node[state, accepting, right of=q3] (q4) {};
	\draw (ii) edge[above] node{$\varepsilon$} (p1);
	\draw (ii) edge[below] node{$\varepsilon$} (q1);
	\draw (p1) edge[above] node{$0$} (p2);
	\draw (p2) edge[above] node{$1$} (p3);
	\draw (q1) edge[above] node{$0$} (q2);
	\draw (q2) edge[above] node{$1$} (q3);
	\draw (q3) edge[above] node{$1$} (q4);
      \end{tikzpicture}
      \bigskip

      \begin{tikzpicture}[fa,baseline={([yshift=-1em] current bounding box.north)}]
	\node at (0,3) {$(01\cup 011)^{*}$:};
	\node[state, initial] (iii) {};
	\node[state, right of=iii] (ii) {};
	\node[state, above right of=ii] (p1) {};
	\node[state, right of=p1] (p2) {};
	\node[state, accepting, right of=p2] (p3) {};
	\node[state, below right of=ii] (q1) {};
	\node[state, right of=q1] (q2) {};
	\node[state, right of=q2] (q3) {};
	\node[state, accepting, right of=q3] (q4) {};
	\draw (iii) edge[above] node{$\varepsilon$} (ii);
	\draw (ii) edge[above] node{$\varepsilon$} (p1);
	\draw (ii) edge[below] node{$\varepsilon$} (q1);
	\draw (p1) edge[above] node{$0$} (p2);
	\draw (p2) edge[above] node{$1$} (p3);
	\draw (q1) edge[above] node{$0$} (q2);
	\draw (q2) edge[above] node{$1$} (q3);
	\draw (q3) edge[above] node{$1$} (q4);
	\draw (q4) edge[below, bend left=35] node{$\varepsilon$} (iii);
	\draw (p3) edge[above, bend right=35] node{$\varepsilon$} (iii);
      \end{tikzpicture}
    \end{sol}

  \item Create an NFA accepting the language $A$ of words ending in an odd
    number of $1$s and an NFA accepting exactly the language $B$ of words ending
    in $0$.  Combine these using the technique from the lecture to create an NFA
    recognizing the concatenation $AB$.
    \medskip

    \begin{sol}
      Homework.
    \end{sol}
  \item 
    Convert the NFA in problem~\ref{01wed:3} into a DFA using the
    method from our text.  Label the states with states describing subsets of the original set
    of states, omitting states corresponding to unreachable states. Each
    state in your DFA should have arrows for~$a$ and for~$b$.
    \medskip

    \begin{sol}
      Homework.
    \end{sol}
\end{enumerate}
\end{document}
