\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, Monday Week 3}
}
\renewcommand{\headrulewidth}{0pt}
}

\begin{document}
\thispagestyle{firststyle}

\bigskip

\begin{prob}
  \begin{enumerate}
    \item Discuss how you would prove that the intersection of a context-free
      language and a regular language is a context-free language.  Afterwards,
      give a written explanation using fewer than three sentences.
    \item Explain how to prove that the set of binary strings with equal numbers of 0s and 1s but
      containing no substring of the form $0100$ or $1001$ is context free.
      Detailed descriptions of machines are not required.
  \end{enumerate}
\end{prob}

\begin{prob}
  Review the precise statement of the pumping lemma for context-free languages.
  \medskip

  Let $\Sigma=\{1,2,3,4\}$ and $L$ be the set of words $w\in\Sigma^{*}$ such
  that the number of~$1$s in~$w$ equals the number of~$2$s in~$w$, and the
  number of $3$s in~$w$ equals the number of~$4$s.  Prove that $L$ is not a CFL. 
\end{prob}

\begin{prob}\label{prob:fri-palindrome}
   Let $\Sigma=\{0,1\}$, and let $P$ be the set of words that are palindromes
   with an equal number of~$0$s and~$1s$:
   $P =\{ww^{R}: w\in\Sigma^{*} \text{and the number of~$0s$ equals the number
   of $1$s in $w$}\}$.  Prove that $P$ is not a CFL.
\end{prob}

\begin{sol}
  We prove this by contradiction using the pumping lemma for CFLs.  Suppose~$P$
  is context-free, and let~$p$ be a pumping length.  Consider the word $w
  =0^{p}1^{p}$ so that~$ww^{R}=0^{p}1^{2p}0^{p}$.  By the pumping lemma, we can
  write $ww^{R}=uvxyz$ with $|vy|>0$, $|vxy|\leq p$, and such that~$uv^{i}xy^{i}z\in L$ for all $i\geq0$.
  Label parts of the word $ww^{R}$ as follows:
  \[
    ww^{R}=\underbrace{0\cdots0}_{a}\underbrace{1\cdots1}_{b}\underbrace{1\cdots1}_{c}\underbrace{0\cdots0}_{d}
  \]
  where each labeled segment has length~$p$.
  Since $|vxy|\leq p$, we must have one of the following:
  \begin{itemize}
    \item $vxy$ is contained in segment~$a$.
    \item $vxy$ is overlaps in segments~$a$ and~$b$.
    \item $vxy$ is contained in segment~$b$.
    \item $vxy$ is overlaps in segments~$b$ and~$c$.
    \item $vxy$ is contained in segment~$c$.
    \item $vxy$ is overlaps in segments~$c$ and~$d$.
    \item $vxy$ is contained in segment~$d$.
  \end{itemize}
  Checking case-by-case, we see that $uv^{2}xy^{2}z\not\in L$, in contradiction
  to the pumping lemma.
\end{sol}

\begin{prob}
  \begin{enumerate}
    \item What is the formal definition of a Turing machine?
    \item Can a Turing machine ever write the blank symbol \textvisiblespace on
      its tape?
    \item Can the tape alphabet $\Gamma$ ever be the same as the input
      alphabet~$\Sigma$?
    \item After executing a transition, is it ever possible that the head of a
      Turing machine is over the same cell it started in?
    \item Can a Turing machine contain just a single state?
  \end{enumerate}
\end{prob}

\begin{prob}
  Give a high-level description with numbered steps of a Turing machine that recognizes the
  palindrome language of Problem~\ref{prob:fri-palindrome}.
\end{prob}

\begin{sol}
  Let the input be $w$.  
  \begin{enumerate}[label=\arabic*.]
    \item If $w$ is empty, accept~$w$.  In other words, if the first tape cell is
      blank, \textbf{accept}~$w$.
    \item Check to see if the length of the input is odd.  If it is,
      \textbf{reject}.  This rules out words like 00100 which do not have the
      form $ww^{R}$.
    \item Otherwise, let $a$ be the symbol under the tape head.
      \begin{enumerate}[label=(\roman*)]
        \item\label{step:03mong} Replace~$a$ with $x$ and scan right until a blank or an $x$ is read.
	\item Move one step to the left.  If the symbol under the tape head is
	  $x$, \textbf{accept}.
	\item If the symbol under the tape head is not~$a$, then
	  \textbf{reject}.  
	\item Otherwise, write an~$x$ and scan to the left until an $x$ is
	  read.  Then move to the right one step, and let $a$ be the symbol
	  under the tape head.  If~$a=x$, accept.  Otherwise, go to
	  step~\ref{step:03mong}.
      \end{enumerate}
  \end{enumerate}
\end{sol}

\begin{prob} (Bonus)
  Consider a Turing machine that cannot write over its input. That is, whatever
  length of string that the input is on cannot be changed, but can be read as
  normal (and the rest of the tape can be changed as normal). Show that Turing
  machines of this type can recognize only regular languages.
\end{prob}
\end{document}
