%\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 2024} }
       \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{January 31}{\bf {February 7}}

{\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^id^j : i,j \ge 0 \}$.

\item $L_2 = \{a^ib^jc^jd^i : i,j \ge 0 \}$.

\item $L_3 = \{a^ib^jc^k : i = j = k \mbox{ or } i > 1000\}$.
\end{enumerate}

\item Identify each of the following languages as either decidable
or undecidable, and prove that your classification is correct,
using the techniques we have developed in this course. Recall that for a context free
grammar $G$, we denote by $L(G)$ the language it describes, and
similarly for a regular expression $E$, we denote by $L(E)$ the
language it describes.

\begin{enumerate}
\item $\mbox{\sc cfl-in-reg} = \{(G, E) : \mbox{$G$ is a CFG, $E$
is a regular expression, and $L(G) \subseteq L(E)$}\}$

\item $\mbox{\sc reg-in-cfl} = \{(E, G) : \mbox{$G$ is a CFG, $E$
is a regular expression, and $L(E) \subseteq L(G)$}\}$
\end{enumerate}

Hint: you may wish to use the fact that the intersection of a context free language and a regular language is context-free (Sipser problem 2.18).


\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 over the alphabet $\Sigma = \{a, b\}$, 
\[L = \{w : w \mbox{ is a palindrome}\},\] 
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{3-IN-A-ROW}_L$ as follows:
\begin{eqnarray*}
\mbox{3-IN-A-ROW}_L & = & \{\#x_1\#x_2\#\cdots\#x_k\# : k \ge 0 \\
& & \;\;\; \mbox{ and for some }i\mbox{, }x_i \in L \mbox{ and } x_{i+1} \in L\mbox{ and } x_{i+2} \in L.\}
\end{eqnarray*}
Prove that $\mbox{3-IN-A-ROW}_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}
