%
% Assignment 4b for CS3530 Computational Theory:
% Turing Machines
% Fall 2023
%
% 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}
\usepackage{multicol}

% 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 4b} \\[2mm]
Fall 2023
\end{center}

\raggedright

\section*{Exercise 4.4 (10 points)}

\subsection*{Problem}

Let $A_{\varepsilon\text{CFG}} = \{ \langle G \rangle | G $ is a CFG that generates $ \varepsilon \}$.  Show that $A_{\varepsilon\text{CFG}}$ is decidable.

\subsection*{Solution}



\section*{Exercise 4.5abcdef (10 points)}

\subsection*{Problem}

Let $X = \{ 1,2,3,4,5 \}$ and $Y = \{ 6,7,8,9,10 \}$.  We describe the
functions $f: X \rightarrow Y$ and $g: X \rightarrow Y$ in the following tables.
Answer each part and give a reason for each answer.

\begin{multicols}{2}
  \begin{tabular}{c|c}
    $n$ & $f(n)$ \\
    \hline
    1 & 6 \\
    2 & 7 \\
    3 & 6 \\
    4 & 7 \\
    5 & 6 \\
  \end{tabular}

  \begin{tabular}{c|c}
    $n$ & $g(n)$ \\
    \hline
    1 & 10 \\
    2 & 9 \\
    3 & 8 \\
    4 & 7 \\
    5 & 6 \\
  \end{tabular}
\end{multicols}

\begin{multicols}{2}
\begin{itemize}
\item [a.] Is $f$ one-to-one?
\item [b.] Is $f$ onto?
\item [c.] Is $f$ a correspondence?
\item [d.] Is $g$ one-to-one?
\item [e.] Is $g$ onto?
\item [f.] Is $g$ a correspondence?
\end{itemize}
\end{multicols}


\subsection*{Solution}

\begin{itemize}
\item [a.] 
\item [b.] 
\item [c.] 
\item [d.] 
\item [e.] 
\item [f.] 
\end{itemize}



\end{document}
