
\documentclass[11pt]{article}
\usepackage{txfonts}
\usepackage{graphicx}
\usepackage{mygb4e}
\usepackage{solution}

%\hidesolutions
\setlength\oddsidemargin{0.01in}
\setlength\topmargin{-1in}
\setlength\textwidth{6.9in}
\setlength\textheight{9.5in} 

\newcommand{\nl}{\mbox{$\langle cr \rangle$}}

\raggedright

\newcommand{\valueof}[1]{\lbrack\!\lbrack #1 \rbrack\!\rbrack}
\newcommand{\refp}[1]{(\protect\ref{#1})}
\def\rwd#1 {\mbox{#1}}
\def\N{\ensuremath{\mathcal{N}}}
\def\implies{\ensuremath{\Rightarrow}}
% Set some text inside an fbox the full width of the line, with the frame
% sticking out into the margin.
\long\def\framepar#1{\par\noindent\hbox to \textwidth {\hskip-\fboxsep
\fbox{\parbox{\the\textwidth}{#1}}}}


\begin{document}
%\setlength{\baselineskip}{12pt}

\begin{center}
{\Large\bf CMPT 379 - Summer 2016 - Sample Midterm}
\end{center}

\begin{comment}
\bigskip

{\large\em Read the instructions below and fill in your name and student id on your Exam Booklet while you wait for the exam to start. {\bf Please write down ``QUIZ \#1'' on the top of the Exam Booklet.} }

\bigskip

{\em Answer all the questions in the Exam Booklet provided to you. 
Do not answer the questions on this paper}.

\bigskip

You can use any space in this question booklet as scratch paper.
Please ask if you need additional scratch paper or exam booklets.
Read all questions carefully, and write your answers clearly and legibly. 

\bigskip

{\em When you have finished, return your Exam Booklet along with this question booklet. }
 
\bigskip
\end{comment}

\begin{exe}

\ex\label{re} (6pts) If the following descriptions define a regular
language then write the corresponding regular expression. Otherwise
indicate that the language is not regular. Provide regular expressions
that are explanatory and compact. Use the usual regular expression
operators: {\tt $\cdot$ $\mid$ $($ $)$ $\ast$}, where the
concatenation operator {\tt $\cdot$} can be omitted.  You can also use
the operator {\tt $?$} which stands for zero or one occurrence of the
previous symbol or group. 

\begin{xlist}

\ex{\label{re0} All strings of 0's and 1's that represent binary
numbers that are equal to the decimal number 6. Leading zeroes must
be allowed.

\begin{soln}
\texttt{0*110}, cut half the points for missing initial \texttt{0*}
\end{soln}
}

\ex{\label{re1} All strings of 0's and 1's that represent binary
numbers that are powers of 2. Leading zeroes must be allowed.

\begin{soln}
\texttt{0*10*}, cut half the points for missing initial \texttt{0*}
\end{soln}
}

\ex{\label{re2} All strings of 0's and 1's that represent Binary Coded
Decimal (BCD) numbers (include the empty string). A BCD number is
a decimal number where each decimal digit is encoded using a 4-bit
representation of its binary value. For example, the BCD number of
2509 is 0010010100001001

\begin{soln}
\texttt{((0(0|1)(0|1)(0|1))|((100)(0|1)))*}
\par\noindent Following solution is also ok:
\par\noindent \texttt{((0000)|(0001)|(0010)|(0011)|(0100)|(0101)|(0110)|(0111)|(1000)|(1001))*}
\end{soln}
}

\end{xlist}

\bigskip

\ex\label{token} (8pts) You are given the following ordered list of token 
definitions:

\begin{tabbing}
123456789\=\kill
{\tt TOKEN\_A} \> $c d a^\ast$ \\
{\tt TOKEN\_B} \> $c^\ast a^\ast c$ \\
{\tt TOKEN\_C} \> $c^\ast b$
\end{tabbing}

Provide the tokenized output for the following input strings using
the greedy longest match lexical analysis method. Provide the list
of tokens and the lexeme values.

\begin{xlist}

{\ex $cdaaab$
\begin{soln}
TOKEN\_A (cdaaa), TOKEN\_C (b)
\end{soln}
}

{\ex $cdccc$
\begin{soln}
TOKEN\_A (cd), TOKEN\_B (ccc)
\end{soln}
}

{\ex $ccc$
\begin{soln}
TOKEN\_B (ccc)
\end{soln}
}

{\ex $cdccd$
\begin{soln}
TOKEN\_A (cd), TOKEN\_B (cc), ERROR (illegal token)
\end{soln}
}

\end{xlist}

\bigskip

  \ex\label{cfg2} (8pts) Consider the following grammar $G$:
  \begin{eqnarray}
    S' & \rightarrow & S \nonumber \\
    S & \rightarrow & aSa \mid bSb \mid aa \mid bb \nonumber
  \end{eqnarray}
      
  \begin{xlist}
    {\ex Is the CFG $G$ an LL($1$) grammar? Provide a reason for your
    answer.
      \begin{soln}
        No. FIRST(aSa) intersected with FIRST(aa) is non-empty.
      \end{soln}
    }

%    {\ex  Based on inspecting the set of possible viable prefixes for
%      grammar $G$, is $G$ an LR(1) grammar? Provide an example viable
%      prefix or a comparison between two candidate viable prefixes to
%      support your answer.
%      \begin{soln}
%        No. While the grammar is unambiguous, consider the potential
%        viable prefix $a^\ast b^\ast a aa a$ and the potential
%        viable prefix $a^\ast b^\ast aa$ -- the same prefix can lead
%        to a shift on $a$ or a reduce using $S \rightarrow aa$ on
%        the handle $a^\ast b^\ast aa$. 
%      \end{soln}
%    }

    {\ex Consider a slightly modified version of grammar $G$. Let's
      call it $G'$:
      \begin{eqnarray}
        S & \rightarrow & aSa \mid bSb \mid \epsilon \nonumber
      \end{eqnarray}
      Does this modified grammar $G'$ generate the same language as
      the original grammar $G$? Provide a reason for your answer.
      \begin{soln}
        No. It now includes $\epsilon$ in the language.
      \end{soln}
    }
    
    {\ex  Is $G'$ an LL($1$) grammar? Provide a reason for your answer.
      \begin{soln}
        No, it is still not an LL($1$) grammar because the intersection
        of FIRST($aSa$) and FOLLOW($S$) = $\{ a, b, \$ \}$ is
        non-empty.
      \end{soln}
    }
    
    {\ex Is the CFG $G'$ an SLR($1$) grammar? Provide a reason for your
    answer.
      \begin{soln}
        No. In the closure for $S' \rightarrow \bullet S$ we get two
        shift-reduce conflicts between $S \rightarrow \epsilon \bullet$
        and $S \rightarrow \bullet aSa$ and $S \rightarrow \bullet bSb$.
        Furthermore, FOLLOW($S$) = $\{ a, b \}$ so the conflicts cannot
        be resolved with one symbol of lookahead in an SLR(1) parser.
      \end{soln}
    }


  \end{xlist}

\bigskip

\newcommand{\cfgrule}[2]{#1 & \rightarrow & #2 \nonumber \\}

\ex\label{derivs} (8pts) Consider the family of CFGs $G_k$ with $S$ as the start symbol and $k$ is some arbitrary non-zero positive integer such that $G_1, G_2, G_3, \ldots$ are individual CFGs with the rules:
\begin{eqnarray*}
\cfgrule{S}{A\ B}
\cfgrule{B}{C\ A\ A}
\cfgrule{C}{c}
\cfgrule{A}{a_i \textrm{\ \ \ defines $i$ rules, where $i \in [1,k]$ }}
\end{eqnarray*}
For example, in $G_3$ the rules with $A$ as left-hand side are: $A \rightarrow a_1 \mid a_2 \mid a_3$ with three terminal symbols.

\begin{xlist}

{\ex Provide the number of terminal symbols in a grammar $G_k$, the number of elements in FIRST($S$), and the number of elements in FOLLOW($C$).
\begin{soln}
$k+1$, $k$, and $k$ respectively.
\end{soln}
}

{\ex If the string $a_3 c a_1 a_2$ is accepted by grammar $G_4$ then provide the leftmost derivation that derives it.
\begin{soln}
$S \Rightarrow A\ B \Rightarrow a_3\ B \Rightarrow a_3\ C\ A\ A \Rightarrow a_3\ c\ A\ A \Rightarrow a_3\ c\ a_1\ A \Rightarrow a_3\ c\ a_1\ a_2$
\end{soln}
}

{\ex Can any $G_k$ grammar have a leftmost derivation of the form: $X \Rightarrow^\ast \alpha X \beta$, where $X$ is any non-terminal in the grammar $G_k$ and $\alpha, \beta$ is any sequence of terminals or non-terminals? Briefly explain why.
\begin{soln}
No. the grammar is not recursive so $X \Rightarrow_{lm}^\ast \alpha X \beta$ for any $X$ cannot occur.
\end{soln}
}

{\ex Provide the total number of leftmost derivations possible for a grammar $G_k$.
\begin{soln}
$k^3$
\end{soln}
}

\end{xlist}  

\end{exe}
\end{document}

