\documentclass[12pt]{article}
\usepackage{amsfonts,amsmath,amssymb}
\usepackage{fullpage}
\usepackage[left=1.0in,top=1.0in,right=1.0in,bottom=1.25in]{geometry}
\usepackage{bbold}
\usepackage{parskip}
\usepackage{tikz}
\usetikzlibrary{topaths,calc,automata,positioning}
\pagenumbering{gobble}


\setlength{\arraycolsep}{4pt}

\begin{document}
\begin{center}
\section*{CS 360 --- Introduction to the Theory of Computing \\ Assignment 4}
\subsection*{University of Waterloo, Spring 2018}
\end{center}
{\it Due 5:00 PM, July 6, 2018.}

\begin{enumerate}
\item Let $L \subseteq \Sigma^*$ be the language 
\begin{equation*}
L = \{w \in \{a,b\}^* \mid |w|_a \neq 2|w|_b \}.
\end{equation*}
Describe a Turing machine that decides $L$.

\item Show that the language
\begin{equation*}
L = \{\langle A,B \rangle \mid \text{$A$ and $B$ are DFAs and $L(A) \cap L(B) \neq \emptyset$} \}
\end{equation*}
is decidable.

\item 
\begin{enumerate}
\item Show that the class of decidable languages is closed under complementation.
\item Show that the class of recognizable languages is closed under intersection.
\item Show that the class of recognizable languages is closed under concatenation.
\end{enumerate}

\item A Turing machine with doubly infinite tape is like the Turing machine we have defined, but its tape is infinite to the left as well as to the right. The tape is initially filled with blanks except for the position that contains the input. Computation is defined as usual except that the head never encounters an end to the tape as it moves leftward. 

Show that this type of Turing machine recognizes the class of Turing-recognizable languages.

\item Let $\Sigma$ be a finite alphabet. We denote by $FIN(\Sigma)$ the set of finite languages over $\Sigma$. That is,
\begin{equation*}
FIN(\Sigma) = \{ L \subseteq \Sigma^* \mid \text{$L$ is finite}\}.
\end{equation*}
Show that $FIN(\Sigma)$ is countable.

\end{enumerate}
\end{document}
