%\documentstyle[10pt,twoside]{article}
\documentstyle[twoside, 11pt]{article}
\setlength{\oddsidemargin}{0.25 in}
\setlength{\evensidemargin}{-0.25 in}
\setlength{\topmargin}{-0.6 in}
\setlength{\textwidth}{6.5 in}
\setlength{\textheight}{8.5 in}
\setlength{\headsep}{0.75 in}
\setlength{\parindent}{0 in}
\setlength{\parskip}{0.1 in}
%
% The following commands sets up the lecnum (lecture number)
% counter and make various numbering schemes work relative
% to the lecture number.
%
\newcounter{lecnum}
\renewcommand{\thepage}{\thelecnum-\arabic{page}}
\renewcommand{\thesection}{\thelecnum.\arabic{section}}
\renewcommand{\theequation}{\thelecnum.\arabic{equation}}
\renewcommand{\thefigure}{\thelecnum.\arabic{figure}}
\renewcommand{\thetable}{\thelecnum.\arabic{table}}
%
% The following macro is used to generate the header.
%
\newcommand{\midterm}[2]{
\pagestyle{myheadings}
\thispagestyle{plain}
\newpage
\setcounter{lecnum}{0}
\setcounter{page}{1}
\noindent
\begin{center}
\framebox{
\vbox{\vspace{2mm}
\hbox to 6.28in { {\bf CS~21~~~Decidability and Tractability
\hfill Winter 2023} }
\vspace{4mm}
\hbox to 6.28in { {\Large \hfill Midterm \hfill} }
\vspace{2mm}
\hbox to 6.28in { {\it Out: #1 \hfill Due: #2} }
\vspace{2mm}}
}
\end{center}
\vspace*{4mm}
}
%
% Convention for citations is authors' initials followed by the year.
% For example, to cite a paper by Leighton and Maggs you would type
% \cite{LM89}, and to cite a paper by Strassen you would type \cite{S69}.
% (To avoid bibliography problems, for now we redefine the \cite command.)
%
\renewcommand{\cite}[1]{[#1]}
\input{epsf}
%Use this command for a figure; it puts a figure in wherever you want it.
%usage: \fig{NUMBER}{FIGURE-SIZE}{CAPTION}{FILENAME}
\newcommand{\fig}[4]{
\vspace{0.2 in}
\setlength{\epsfxsize}{#2}
\centerline{\epsfbox{#4}}
\begin{center}
Figure \thelecnum.#1:~#3
\end{center}
}
% Use these for theorems, lemmas, proofs, etc.
\newtheorem{theorem}{Theorem}[lecnum]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}[theorem]{Definition}
\newenvironment{proof}{{\bf Proof:}}{\hfill\rule{2mm}{2mm}}
% Some useful equation alignment commands, borrowed from TeX
\makeatletter
\def\eqalign#1{\,\vcenter{\openup\jot\m@th
\ialign{\strut\hfil$\displaystyle{##}$&$\displaystyle{{}##}$\hfil
\crcr#1\crcr}}\,}
\def\eqalignno#1{\displ@y \tabskip\@centering
\halign to\displaywidth{\hfil$\displaystyle{##}$\tabskip\z@skip
&$\displaystyle{{}##}$\hfil\tabskip\@centering
&\llap{$##$}\tabskip\z@skip\crcr
#1\crcr}}
\def\leqalignno#1{\displ@y \tabskip\@centering
\halign to\displaywidth{\hfil$\displaystyle{##}$\tabskip\z@skip
&$\displaystyle{{}##}$\hfil\tabskip\@centering
&\kern-\displaywidth\rlap{$##$}\tabskip\displaywidth\crcr
#1\crcr}}
\makeatother
% **** IF YOU WANT TO DEFINE ADDITIONAL MACROS FOR YOURSELF, PUT THEM HERE:
\newcommand{\remove}[1]{}
\begin{document}
\midterm{February 1}{\bf {February 8}}
{\bf This is a midterm.} You may consult only the course notes and
the text (Sipser). {\em You may not collaborate.} The full honor code guidelines can be found in the course syllabus.
There are 5 problems
on 2 pages. Please attempt all problems. {\bf Please turn in your solutions via
Gradescope, by 1pm on the due date.} Good luck!
\begin{enumerate}
\item Identify each of the following languages as either (i)
regular, (ii) context-free but not regular, or (iii) not
context-free. For each language, prove that your classification is
correct, using the techniques we have developed in this course.
\begin{enumerate}
\item $L_1 = \{a^ib^jc^k : j > i+k \}$.
\item $L_2 = \{a^ib^jc^k : i = j = k \mbox{ or } i > 1000\}$.
\item $L_3 = \{a^ib^jc^k : i = j = k \mbox{ or } i < 1000\}$.
\end{enumerate}
\item A state $q$ of a deterministic Turing Machine $M$ is {\em reachable} if
there is some string $w$ for which $M$'s computation on $w$ enters
state $q$. Otherwise, it is {\em unreachable}. Consider the following language:
\[L = \{\langle M \rangle : \mbox{Turing Machine } M \mbox{ has an unreachable state}.\}\]
\begin{enumerate}
\item Determine if $L$ is RE or co-RE, and prove that your
classification is correct.
\item Prove that $L$ is undecidable. Hint: you may want to take a
given Turing Machine $M$, and modify it so that before it enters
$q_{\mbox{accept}}$, it visits {\em all} of its states. To do
this, introduce a new character $\%$ to the tape alphabet, and new
transitions that take the machine on a tour of its states when it
reads this special character...
\end{enumerate}
\item Two (disjoint) languages $L_1$ and $L_2$ are called {\em
recursively separable} if there is a decidable language $D$ for
which $L_1 \cap D = \emptyset$ and $L_2 \subseteq D$; they are
{\em recursively inseparable} if no such decidable language $D$
exists. Convince yourself that an undecidable language and its
complement are recursively inseparable.
Consider the following languages:
\begin{eqnarray*}
L_1 & = & \{\langle M \rangle : M \mbox{ halts and accepts input
} \langle
M \rangle\} \\
L_2 & = & \{\langle M \rangle : M \mbox{ halts and rejects input
} \langle M \rangle\}
\end{eqnarray*}
Prove that $L_1$ and $L_2$ are recursively inseparable. Hint: your
proof will probably involve supplying a Turing Machine its own
description as input.
\newpage
\item A {\em right-linear} CFG is a context-free grammar in which
every production has the form
\begin{itemize}
\item $A \rightarrow xB$, or
\item $A \rightarrow x$,
\end{itemize}
where $A$ and $B$ are non-terminals, and $x$ can be any string of
terminals. A CFG is {\em linear} if productions of the form $A
\rightarrow Bx$ are allowed in addition to the two types of
productions in a right-linear CFG.
\begin{enumerate}
\item Prove that every language generated by a right-linear CFG is
regular.
\item Prove that every regular language is generated by some
right-linear CFG.
\item Give a linear CFG that generates the non-regular
language
\[L = \{a^nb^n : n \ge 0\}\]
and prove that your grammar indeed generates exactly $L$ (i.e., prove that every string in $L$ is generated by your grammar, and prove that every string generated by your grammar is in $L$).
\end{enumerate}
\item Given a language $L$, define $\mbox{AT-LEAST-50}_L$ as follows:
\begin{eqnarray*}
\mbox{AT-LEAST-50}_L & = & \{\#x_1\#x_2\#\cdots\#x_k\# : k \ge 0 \mbox{ and } |\{i : x_i \in L\}| \ge 50.\}
\end{eqnarray*}
Prove that $\mbox{AT-LEAST-50}_L$ is RE if L is RE. Here the $x_i$
are strings over $L$'s alphabet, and $\#$ is a symbol that is not
in $L$'s alphabet.
\end{enumerate}
\end{document}