%
% Assignment 3a for CS3530 Computational Theory:
% Turing Machines
% Fall 2024
%
% Problems taken from Sipser
%

\documentclass{article}

\usepackage[margin=1in]{geometry}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage[english]{babel}
\usepackage[utf8]{inputenc}
\usepackage{ae,aecompl}
\usepackage{enumerate}

% skip for paragraphs, don't indent
\parskip 6pt plus 1pt
\parindent=0pt
\raggedbottom

% a list environment with no bullets or numbers
\newenvironment{indentlist}{\begin{list}{}{\addtolength{\itemsep}{0.5\baselineskip}}}{\end{list}}

\begin{document}
\begin{center}
\textbf{\Large CS 3530: Assignment 3a} \\[2mm]
Fall 2024
\end{center}

\raggedright

\section*{Exercise 3.1c (10 points)}

\subsection*{Problem}

This exercise concerns TM $M_2$ whose description and state diagram appear in Example
3.7.   In each of the parts, give the sequence of configurations that $M_2$ enters when
started on the indicated input string.

\begin{itemize}
\item [c.] $000$
\end{itemize}

\subsection*{Solution}

\begin{itemize}
\item [c.] You may wish to know that $\sqcup$ gives the symbol for blank.
\end{itemize}

\section*{Exercise 3.8b (10 points)}

\subsection*{Problem}

Give implementation-level descriptions of Turing machines that decide the following
languages over the alphabet $\{0,1\}$.

\begin{itemize}
\item [b.] $\{ w | w $ contains twice as many $0$s as $1$s $ \}$
\end{itemize}

\subsection*{Solution}

\begin{itemize}
\item [b.] Format your answer like $M_1$ in the chapter.  For example:
  
  Let $M_{3.8b} = $ ``On input string $w$:
\begin{enumerate}
\item Do some operation
\item Repeat for some conditions
\item \hspace{0.1in} Body of loop
\item \hspace{0.1in} Body of Loop
\item If SOMETHING, then \emph{accept}.  Otherwise, \emph{reject}.''
\end{enumerate}

\end{itemize}


\end{document}
