<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">%\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 2025} }
       \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{##}$&amp;$\displaystyle{{}##}$\hfil
      \crcr#1\crcr}}\,}
\def\eqalignno#1{\displ@y \tabskip\@centering
  \halign to\displaywidth{\hfil$\displaystyle{##}$\tabskip\z@skip
    &amp;$\displaystyle{{}##}$\hfil\tabskip\@centering
    &amp;\llap{$##$}\tabskip\z@skip\crcr
    #1\crcr}}
\def\leqalignno#1{\displ@y \tabskip\@centering
  \halign to\displaywidth{\hfil$\displaystyle{##}$\tabskip\z@skip
    &amp;$\displaystyle{{}##}$\hfil\tabskip\@centering
    &amp;\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 5}{\bf {February 12}}

{\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 \le i+k \}$.

\item $L_2 = \{a^ib^jc^k : i = j = k \mbox{ or } i &gt; 1000\}$.

\item $L_3 = \{a^ib^jc^k : i = j = k \mbox{ or } i &lt; 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 it accepts the
    same set of strings, but 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... If you are stuck, you can take
    this transformation as a given and describe a reduction using it, for
    partial credit. 
  \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 &amp; = &amp; \{\langle M \rangle  : M \mbox{ halts and accepts input
} \langle
M \rangle\} \\
L_2 &amp; = &amp; \{\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 &amp; = &amp; \{\#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}
</pre></body></html>