%\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 2012} }
       \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.}  There are 5 problems
on 2 pages. Please attempt all problems. {\bf To facilitate
grading, please turn in each problem on a separate sheet of paper
and put your name on each sheet. Do not staple the separate
sheets.} 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 : j = ik \}$.

\item $L_3 = \{a^ib^jc^k : i = j = k \mbox{ or } ijk > 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
\[L = \{0^n1^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{MAJORITY}_L$ as follows:
\[\mbox{MAJORITY}_L = \{\#x_1\#x_2\#\cdots\#x_k\# : k \ge 0 \mbox{ and $|\{i:x_i \in L\}| > k/2$}\}.\]
Prove that $\mbox{MAJORITY}_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}