\documentclass[12pt,a4paper]{article}
\usepackage{ctex}
\usepackage{amsmath,amscd,amsbsy,amssymb,latexsym,url,bm,amsthm,mathrsfs}
\usepackage{epsfig,graphicx,subfigure}
\usepackage{enumitem,balance,mathtools}
\usepackage{wrapfig}
\usepackage{mathrsfs, euscript}
\usepackage[usenames]{xcolor}
\usepackage{hyperref}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{exercise}{Exercise}[section]
\newtheorem*{solution}{Solution}

\numberwithin{equation}{section}

\renewcommand{\thefootnote}{\fnsymbol{footnote}}

\newcommand{\postscript}[2]
 {\setlength{\epsfxsize}{#2\hsize}
  \centerline{\epsfbox{#1}}}

\renewcommand{\baselinestretch}{1.0}

\setlength{\oddsidemargin}{-0.365in}
\setlength{\evensidemargin}{-0.365in}
\setlength{\topmargin}{-0.3in}
\setlength{\headheight}{0in}
\setlength{\headsep}{0in}
\setlength{\textheight}{10.1in}
\setlength{\textwidth}{7in}
\makeatletter \renewenvironment{proof}[1][Proof] {\par\pushQED{\qed}\normalfont\topsep6\p@\@plus6\p@\relax\trivlist\item[\hskip\labelsep\bfseries#1\@addpunct{.}]\ignorespaces}{\popQED\endtrivlist\@endpefalse} \makeatother
\makeatletter
\renewenvironment{solution}[1][Solution] {\par\pushQED{\qed}\normalfont\topsep6\p@\@plus6\p@\relax\trivlist\item[\hskip\labelsep\bfseries#1\@addpunct{.}]\ignorespaces}{\popQED\endtrivlist\@endpefalse} \makeatother
\begin{document}
\noindent

%========================================================================
\noindent\framebox[\linewidth]{\shortstack[c]{
\Large{\textbf{Lab14-Computability}}\vspace{1mm}\\
CS101-�������ѧ���ۿκ���ҵ����ʦ��John Hopcroft��2016 �＾ѧ��}}
%\vspace{1mm}
\begin{center}
\footnotesize{\color{red}$*$ �ɴ�ӡ��ҳֱ����ҳ������/��ֽװ������ע����\quad ������\_\_\_\_\_\_\_\_\_\_\_\_ \quad ѧ�ţ�\_\_\_\_\_\_\_\_\_\_\_ \quad �༶��\_\_\_\_\_\_}

\footnotesize{\color{blue}$*$ ���Ӱ���ҵ��ֱ���ϴ����γ���վ}
\end{center}

\begin{enumerate}
\item The set of all finite length strings over a finite alphabet is countably infinite. What is the cardinality of the set of finite length strings over a countably infinite alphabet?

\item The {\color{purple}transition function} (also named as \emph{instruction} or \emph{specification}) of a Turing Machine (TM) $\delta: S \times \Gamma \rightarrow S \times \Gamma \times \{L,R\}$ describes the rules of each computation step. E.g., $\langle q_i, 1 \rangle \rightarrow \langle q_j, 0, R \rangle$ means when reads an ``1" on the tape with the current state as $q_i$, the TM will turn to the state $q_j$, replace the ``1" as a ``0", and then move one cell to the right.
    
    Given $\Sigma=\{0,1\}$, $\Gamma=\{0,1,b\}$ ($b$ as blank symbol appears initially in all except the finite number of inputs), design an one-tape TM $M=(Q, \Sigma, \Gamma, \delta, q_0, b, F)$ to accomplish the ``copy" operation, whose initial configuration is $n$ ``1"'s, and the output should be two series of $n$ ``1"'s with a 0 as separation (Shown as follows).  Describe your design  and write down its transition functions.

\begin{center}
\hspace{-1cm}
\begin{tabular}{l|l|l|l|l|l|l|l|l|l|l|l|lll}
%\multicolumn{15}{c}{Inputs and Outputs on the Tape}\\[5pt]
\cline{2-13}
Input: & 1 & 1 & $\cdots$ &1 & b & b & b & $\cdots$ &  \\
\cline{2-13}
\multicolumn{1}{c}{} & \multicolumn{11}{l}{\color{blue} $\uparrow$ $n$ ``1"'s}\\[4pt]
\cline{2-13}
Output:& 1 & 1 & $\cdots$ &1&0&1&1& $\cdots$ & 1 & b & b & $\cdots$\\
\cline{2-13}
\multicolumn{1}{c}{} & \multicolumn{5}{l}{\color{blue} $\uparrow$ $n$ ``1"'s} & \multicolumn{5}{l}{\color{blue} $\uparrow$ Another $n$ ``1"'s}\\[4pt]
\end{tabular}
\end{center}

\item Construct an Nondeterministic Finite Automaton (NFA) to accept all strings that start and end with the same symbol (with size $|s| \ge 1$) , and convert this NFA into a Deterministic Finite Automaton (DFA).

\end{enumerate}
%========================================================================
\end{document}
