\documentclass{article}

\usepackage{hevea,paralist,amssymb,amsmath}

\oddsidemargin 0cm
\textwidth 17cm

\begin{document}

\thispagestyle{empty}

\begin{center}
{\large\bf  CS 3100 -- SOLUTIONS to mock Final Exam -- TOTAL 100 points}
\end{center}


\noindent The
multiple choice problems given here can earn you positive points (correct
answer) or and negative points (incorrect). We show it as {\bf [+m/-n]}.
%
You must write a compact two-sentence (approx.)
 explanation in support of your
answer, without which you won't gain any points.
{\bf You must put a check mark ($\surd$) in one of the squares
 associated with each question.}
\begin{center}
{\large\bf PART-1} is similar to that of Midterm-2; just giving more practice below
\end{center}
\begin{enumerate}
%=================================================================
\item {\bf [+5/-1]}
{\bf Choose from various answers below.}

\begin{list}{}{\addtolength{\itemsep}{1\itemsep}}
\item A. A DFA reads its input fully before accepting a string
  {\sf Yes; this is by definition so.}

\item B. A multi-tape TM is equivalent to a single tape TM
  {\sf Yes; read how single tape can be simulated.}

\item C. A DTM may accept a string without reading its input
  {\sf Yes; a TM is a generalized computational device. It
  may be designed to read part of its input, skip over the
  rest and go into a loop. As a matter of fact,
  we can't force it to be always
  reading all of the input.}

\item D. The number of configurations of an LBA
  is fixed by its number of states $Q$.
  {\sf No; it also depends on the input length and the tape
    alphabet size.}
\end{list}



\begin{list}{$\square$}{\addtolength{\itemsep}{1\itemsep}}

\item All these assertions are true.

\item Assertions A, B, and C are true. {\sf This one.}

\item Assertion A and C alone are true.

\item Assertions A and D are true.

\end{list}
\noindent{\bf Explanation:\/} See above.

%\vspace{.6cm}

\item {\bf [+5/-1]}
{\bf Choose from various answers below.}
The Schr\"{o}der-Bernstein Theorem

\begin{list}{}{\addtolength{\itemsep}{1\itemsep}}
\item A. helps establish a bijection
  between two sets A and B by finding two one-to-one onto
  functions $f : A\rightarrow B$
  and $g:B\rightarrow A$. {\sf No; see below.}

\item B.  $\ldots$ by finding two one-to-one into
  functions $f : A\rightarrow B$
  and $g:B\rightarrow A$. {\sf This one; the advantage is
    to require only 1-1 into maps.}

\item C. was used in class to show that the number of C programs
  is countably large. {\sf Yes indeed.}

\item D. is another way to present the Diagonalization proof. {\sf No.}
\end{list}


\begin{list}{$\square$}{\addtolength{\itemsep}{1\itemsep}}

\item None of these assertions are true.

\item Assertion A alone is true.

\item All assertions except A are true.

\item Assertions B and C alone are true. {\sf This one.}

\end{list}
\noindent{\bf Explanation:\/} See above.


\item {\bf [+5/-1]}
Consider these assertions.

\begin{list}{}{\addtolength{\itemsep}{1\itemsep}}
\item A. CFLs are closed under intersection. {\sf No; consider
    $a^m b^n c^n$ and $a^m b^m c^n$.}

\item B. RE languages are closed under intersection. {\sf Yes;
    one can run TMs one after the other to get a TM for
    the intersection.}

\item C. RE languages are closed under complementation. {\sf No;
    Else every language will be recursive.}

\item D. Either a language $L$ is RE or its complement
  $\overline{L}$ is RE. {\sf No; there are non-RE languages whose
    complements are also non-RE.}
% CFLs are closed under complementation.
% countability m1 = m2 , m1 != m2..
\end{list}


\begin{list}{$\square$}{\addtolength{\itemsep}{1\itemsep}}

\item All of these assertions are true.

\item Assertion B alone is true. {\sf This one.}

\item All assertions except A are true.

\item Assertions B and D alone are true.

\end{list}

\noindent{\bf Explanation:\/} See above.

%-----------------------------------------------------------------
\item {\bf [+5/-1]}
Consider the Pumping Lemma proofs discussed in this course; call
 them RPL and CPL for the regular and context-free Pumping lemmas.
Recall that the main parts of these PLs are as follows:
(i)~in RPL,  a string $uvw\in L\Rightarrow \;\forall i:\; uv^iw\in L$.
(ii)~in CPL,  a string $uvwxy\in L\Rightarrow \;\forall i:\; uv^iwx^iy\in L$.
Now consider the assertions.

\begin{list}{}{\addtolength{\itemsep}{1\itemsep}}
\item A. In RPL, $v\neq \varepsilon$ because
  the language $L$ is not empty {\sf No.}

\item B. In CPL, $vx\neq \varepsilon$ because the grammar
  of $L$ is assumed to be unambiguous. {\sf No.}

\item C. In RPL, $v\neq \varepsilon$ because
  the loop in the DFA has a length of at least 1. {\sf Yes.}

\item D. In CPL, $vx\neq \varepsilon$ because the grammar
  of $L$ is assumed to be in the Chomsky Normal form. {\sf Yes.}
\end{list}

\begin{list}{$\square$}{\addtolength{\itemsep}{1\itemsep}}

\item Assertions A, B, and C are true

\item Assertions C and D are true {\sf This one.}

\item Assertion C alone is true

\item Assertions A, C, and D are true

\end{list}

\noindent{\bf Explanation:\/} If $vx=\varepsilon$, we will have some
non-terminal {\tt V}
lying along one path from the root to the leaves
that supports two distinct parse trees spanning
string $uwy$ with the upper occurrence of {\tt V} (see a diagram depicting the
CFL Pumping Lemma, such as the one below) having some $\varepsilon$
derivations. But in a Chomsky normal form grammar, a {\tt V} that is 
not the same as {\tt S} cannot have a $\varepsilon$ derivation.

Now you might say that the {\tt V} itself is {\tt S}. But then, 
we have two facts: (i)~only {\tt S} can have the $\varepsilon$ production,
and (ii)~the other non-terminals cannot involve {\tt S} in their right-hand
sides (the grammar is turned into a form where {\tt S} is allowed to refer to
other non-terminals, but not vice versa).

With these constraints, we cannot have both $v$ and $x$ turn into $\varepsilon$.

\begin{verbatim}

         S
         .
         .
         V
        /. \
       / .  \
      /  .   \
     /   V    \
    /   /.\    \
   /   / . \    \
  /   /  .  \    \
uuvvvvwwwwwwwxxxxxyyyy
\end{verbatim}


%=================================================================
\end{enumerate}
%\clearpage
%=================================================================
\begin{center}
{\large\bf PART-2} will be similar to that of Midterm-2
\end{center}

\end{document}
