\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 2}
}
\renewcommand{\headrulewidth}{0pt}
}

\begin{document}
\thispagestyle{firststyle}

\begin{prob}
  Let $A$ be the following CFG from our text (Example 2.25):
  \begin{align*}
    S &\to aTb|b\\
    T &\to Ta|\varepsilon.
  \end{align*}
  The text describes the construction for the following PDA that recognizes
  $L(A)$:
  \begin{center}
    \begin{tikzpicture}[fa,baseline={([yshift=-1em] current bounding box.north)}]
      \node[state, initial] (s) {$q_{\mathrm{start}}$};
      \node[state, right of=s,xshift=1cm] (l) {$q_{\mathrm{loop}}$};
      \node[state, accepting, right of=l,xshift=1cm] (a) {$q_{\mathrm{accept}}$};
      \draw (s) edge[above] node{$\varepsilon,\ \varepsilon\to S\$$} (l);
      \draw (l) edge[loop above, above] node{loop} (l);
      \draw (l) edge[above] node{$\varepsilon,\ \$\to \varepsilon$} (a);
    \end{tikzpicture}
  \end{center}
  The loop has the following transitions:
  \begin{align*}
    \varepsilon,\ S&\to aTb|b \\
    \varepsilon,\ T&\to Ta|\varepsilon\\
    a,\ a  &\to \varepsilon\\
    b,\ b  &\to \varepsilon.
  \end{align*}
  Here, for instance, the notation $\varepsilon,\ S\to aTb|b$ is shorthand for
  two transitions: $\varepsilon,\ S\to aTb$ and $\varepsilon,\ S\to b$.  Also,
  for example, the transition $\varepsilon,\ S\to aTb$, means that if $S$ is at
  the top of the stack, one can pop $S$ and push $aTb$ without reading any
  input.
  \begin{enumerate}
    \item Describe $L(A)$.
    \item Show how the PDA accepts $aaab$ one step at a time.  List the new
      state, the transition, and the stack.  The first step is
      \[
	\begin{array}{c|ll}
	  \text{transition} &q_{\mathrm{start}}\xrightarrow{\varepsilon,
	  \varepsilon\to S\$}  & q_{\mathrm{loop}} \\\hline
	  \text{stack} & \text{empty}\xrightarrow{\qquad} & S\$ 
	\end{array}
      \]
  \end{enumerate}
\end{prob}

\begin{sol}
  \begin{enumerate}
    \item $L(A)$ is described by the regular expression $a^{*}b$.
    \item 
      \[
        \begin{array}{lllll}
        q_{\mathrm{start}}\xrightarrow{\varepsilon, \varepsilon\to S\$}  
	& 
	q_{\mathrm{loop}}\xrightarrow{\varepsilon,\ S\to aTb}
	& 
	q_{\mathrm{loop}}\xrightarrow{\varepsilon,\ a\to \varepsilon}
	& 
	q_{\mathrm{loop}}\xrightarrow{\varepsilon,\ T\to Ta}
	& 
	q_{\mathrm{loop}}
	\\\hline
        \text{empty}\xrightarrow{\qquad} 
	& 
	  S\$\quad\ \ \xrightarrow{\qquad}
	& aTb\$\ \ \xrightarrow{\qquad}
	& 
	  Tb\ \ \xrightarrow{\qquad}
	&
	Tab\$
        \end{array}
      \]
      \medskip

      \[
        \begin{array}{lllll}
	q_{\mathrm{loop}}\xrightarrow{\varepsilon,\ T\to Ta}
	& 
	q_{\mathrm{loop}}\xrightarrow{\varepsilon,\ T\to \varepsilon}
	& 
	q_{\mathrm{loop}}\xrightarrow{a,\ a\to \varepsilon}
	& 
	q_{\mathrm{loop}}\xrightarrow{a,\ a\to \varepsilon}
	& 
	q_{\mathrm{loop}}
	\\\hline
	 Tab\$\ \ \xrightarrow{\qquad}
	& 
	Taab\$\ \ \xrightarrow{\qquad}
	& 
	aab\$\ \ \xrightarrow{\qquad}
	& 
	ab\$\ \ \xrightarrow{\qquad}
	& 
	b\$
        \end{array}
      \]
      \medskip

      \[
        \begin{array}{lll}
	q_{\mathrm{loop}}\xrightarrow{b,\ b\to \varepsilon}
	& 
	q_{\mathrm{loop}}\xrightarrow{\$,\ \$\to \varepsilon}
	& 
	q_{\mathrm{accept}}
	\\\hline
	 b\$\ \ \xrightarrow{\qquad}
	& 
	\$\quad\ \xrightarrow{\qquad}
	& 
	\mathrm{empty}.
        \end{array}
      \]
  \end{enumerate}
\end{sol}

\begin{prob}  Let~$\Sigma=\{0,1\}$, and consider the language $L=\{w: w \text{ contains at least three $1$s}\}$.
  \begin{enumerate}
    \item Find a regular expression for~$L$.
    \item Convert that regular expression into an NFA recognizing $L$.
    \item Find a CFG for the language. 
    \item Convert your CFG into a PDA using the algorithm in the text (as in Problem 1).  
  \end{enumerate}
\end{prob}

\begin{sol}
  \begin{enumerate}
    \item A regular expression for~$L$ is
      $\Sigma^{*}1\Sigma^{*}1\Sigma^{*}1\Sigma^{*}$. 
    \item A corresponding NFA:
      \begin{center}
	\begin{tikzpicture}[fa,baseline={([yshift=-1em] current bounding box.north)}]
	  \node[state, initial] (s) {$q_{0}$};
	  \node[state, right of=s] (l1) {$q_{1}$};
	  \node[state, right of=l1] (l2) {$q_{2}$};
	  \node[state, accepting, right of=l2] (l3) {$q_{3}$};
	  \draw (s) edge[loop above, above] node{$0,1$} (l);
	  \draw (s) edge[above] node{$1$} (l1);
	  \draw (l1) edge[loop above, above] node{$0,1$} (l1);
	  \draw (l1) edge[above] node{$1$} (l2);
	  \draw (l2) edge[loop above, above] node{$0,1$} (l2);
	  \draw (l2) edge[above] node{$1$} (l3);
	  \draw (l3) edge[loop above, above] node{$0, 1$} (l3);
	\end{tikzpicture}
      \end{center}
    \item The algorithm from gives the corresponding CFG:
      \begin{align*}
	S&\to q_{0}\\
	q_{0}&\to 0q_{0}|1q_{0}|1q_{1}\\
	q_{1}&\to 0q_{1}|1q_{1}|1q_{2}\\
	q_{2}&\to 0q_{2}|1q_{2}|1q_{3}\\
	q_{2}&\to 0q_{2}|1q_{2}|1q_{3}\\
	q_{3}&\to 0q_{3}|1q_{3}|\varepsilon.
      \end{align*}
    \item  The corresponding PDA:
      \begin{center}
	\begin{tikzpicture}[fa,baseline={([yshift=-1em] current bounding box.north)}]
	  \node[state, initial] (s) {$q_{\mathrm{start}}$};
	  \node[state, right of=s,xshift=1cm] (l) {$q_{\mathrm{loop}}$};
	  \node[state, accepting, right of=l,xshift=1cm] (a) {$q_{\mathrm{accept}}$};
	  \draw (s) edge[above] node{$\varepsilon,\ \varepsilon\to S\$$} (l);
	  \draw (l) edge[loop above, above] node{loop} (l);
	  \draw (l) edge[above] node{$\varepsilon,\ \$\to \varepsilon$} (a);
	\end{tikzpicture}
      \end{center}
      The loop has the following transitions:
      \begin{align*}
	\varepsilon,\ S&\to Q_{0}\\\
	\varepsilon,\ Q_{0}&\to 0Q_{0}|1Q_{0}|1Q_{1}\\
	\varepsilon,\ Q_{1}&\to 0Q_{1}|1Q_{1}|1Q_{2}\\
	\varepsilon,\ Q_{2}&\to 0Q_{2}|1Q_{2}|1Q_{3}\\
	\varepsilon,\ Q_{2}&\to 0Q_{2}|1Q_{2}|1Q_{3}\\
	\varepsilon,\ Q_{3}&\to 0Q_{3}|1Q_{3}|\varepsilon\\
	0,\ 0  &\to \varepsilon\\
	1,\ 1  &\to \varepsilon.
      \end{align*}
  \end{enumerate} 
\end{sol}

\begin{prob} Let $\Sigma=\{0,1\}$, and consider the language $L=\{0^{m}1^{n}: m\neq n\}$.
  \begin{enumerate}
    \item Find a CFG generating~$L$ using at most three variables.  
    \item Convert your CFG into a PDA using the algorithm in the text (as in
      Problem 1).
    \item Is $L$ regular?  Prove or disprove.
  \end{enumerate}
\end{prob}

\begin{prob} (Bonus)
Our goal in this problem is to show that the representation of objects can
affect whether or not a given set can be recognized by a machine. Consider a
set~$A$ of natural numbers. Let $B_k(A)$ be the set of strings that represent
numbers from~$A$ in base~$k$ (with no leading zeros). For example, if $A = \{3,
5\}$ then $B_2(A) = \{11, 101\}$ and $B_3(A) = \{10, 12\}$. We can think of
$B_k(A)$ as a language with a $k$-symbol alphabet. Give a set~$A$ for which
$B_2(A)$ is regular but $B_3(A)$ is not (and prove it).
\end{prob}
\end{document}
