\documentclass[12pt,a4paper,twoside]{article}  % Comments after  % are ignored
\usepackage{amsmath,amssymb,amsfonts}          % Typical maths resource packages
\usepackage{hyperref}                          % For creating hyperlinks in cross references
\usepackage{pstricks}

\pagestyle{headings}         % Option to put page headers
                             % Needed \documentclass[a4paper,twoside]{article}

%\textwidth 17.5cm
%\rightmargin 1in

%\topmargin -1cm
%\parindent 0cm
%\textheight 24cm
%\parskip 1mm

%\theoremindent .5in
%\newtheorem{definition}[theorem]{Definition}

% Changes the numbering format to a, b, c...
\renewcommand{\theenumi}{\alph{enumi}}
\renewcommand{\labelenumi}{\theenumi.}

\author{Will Holcomb \small{CSC445 - Homework \#3}}
\title{Homework \#3}
\date{October 16, 2002}

\begin{document}
\maketitle

\section{Number 1: Exercise 5.1.2}
Show leftmost and rightmost derivations given the grammar:
\begin{eqnarray}
S &\rightarrow& A1B \nonumber\\
A &\rightarrow& 0A | \epsilon \nonumber\\
B &\rightarrow& 0B | 1B | \epsilon
\end{eqnarray}

\begin{enumerate}

\item 00101 found in Table~\ref{5.1.2.a}

\begin{table}
\begin{tabular}{c || c }
Leftmost & Rightmost \\
\hline\hline
$S$             & $S$ \\
$A1B$           & $A1B$ \\
$0A1B$          & $A10B$ \\
$00A1B$         & $A101B$ \\
$00\epsilon1B$  & $A101\epsilon$ \\
$0010B$         & $0A101$ \\
$00101B$        & $00A101$ \\
$00101\epsilon$ & $00\epsilon101$ \\
$00101$         & $00101$
\end{tabular}
\caption{Right and leftmost expansions for 00101}\label{5.1.2.a}
\end{table}

\item 1001 found in Table~\ref{5.1.2.b}

\begin{table}
\begin{tabular}{c || c}
Leftmost & Rightmost \\
\hline\hline
$S$             & $S$ \\
$A1B$           & $A1B$ \\
$\epsilon1B$    & $A10B$ \\
$10B$           & $A100B$ \\
$100B$          & $A1001B$ \\
$1001B$         & $A1001\epsilon$ \\
$1001\epsilon$  & $\epsilon1001$ \\
$1001$          & $1001$
\end{tabular}
\caption{Right and leftmost expansions for 1001}\label{5.1.2.b}
\end{table}

\item 00011 found in Table~\ref{5.1.2.c}

\begin{table}
\begin{tabular}{c || c }
Leftmost & Rightmost \\
\hline\hline
$S$             & $S$ \\
$A1B$           & $A1B$ \\
$0A1B$          & $A11B$ \\
$00A1B$         & $A11\epsilon$ \\
$000A1B$        & $0A11$ \\
$000\epsilon1B$ & $00A11$ \\
$00011B$        & $000A11$ \\
$00011\epsilon$ & $000\epsilon11$ \\
$00011$         & $00011$
\end{tabular}
\caption{Right and leftmost expansions for 00011}\label{5.1.2.c}
\end{table}

\end{enumerate}

\section{Number 2: Exercise 5.1.7}

\begin{enumerate}

\item Prove by induction that:
\begin{equation}
w = x\textrm{ba}y \not \in L(G) \ni G = S \rightarrow \textrm{a}S |
S\textrm{b} | \textrm{a} | \textrm{b}
\end{equation}

The shortest possible candidate string is when $x = y = \epsilon$; $w
= \textrm{ba}$. This $w \not \in L(G)$. If $|x| = 1$, then $x$ will
consist of a single a or b$\ldots$ In short, the expansion of a's will
always occur at the front of the string and will not follow any b's
because the a's are growing to the right and the b's to the left and
there isn't a way for the two to cross.

\item The regular expression for this language is:
\begin{equation}
L(G) = (a^*b^+|a^+b^*)
\end{equation}

\end{enumerate}

\section{Number 3: Exercise 5.3.1}

Prove that a set of parenthesis is balanced iff it is generated by the
grammar (uses iso ebnf syntax to avoid ambiguity):
\begin{equation}
B = (B, B) | '(', B, ')' | ;
\end{equation}

A string of parenthesis is balanced iff it is scan balanced, that is
if the number of open parenthesis counted scanning from left to right
is always greater than or equal to the number of close parenthesis and
the total numbers are equal.

There is only one expansion that actually inserts parentheses in this
grammar and it inserts an open parenthesis before a close
parenthesis. This means that the count of open parenthses will always
have to be greater than or equal, and also the totals will have to be
equal. Therefore the strings produced will be scan balanced and thus
balanced.

\section{Number 4: Exercise 5.3.5}

Give a grammar for (uses iso ebnf syntax to avoid ambiguity):

DOCTYPE CourseSpecs [ \\
  ELEMENT COURSES (COURSE+) \\
  ELEMENT COURSE (CNAME, PROF, STUDENT*, TA?) \\
  ELEMENT CNAME (\#PCDATA) \\
  ELEMENT STUDENT (\#PCDATA) \\
  ELEMENT TA (\#PCDATA) ]

\begin{eqnarray}
\textrm{courses}               &=& \textrm{course list}; \\
\textrm{course list}           &=& \textrm{course}, \textrm{course list}; \\
\textrm{course}                &=& \textrm{name}, \textrm{professor},
                                    \textrm{optional student list},
                                    \textrm{optional assistant}; \\
\textrm{name}                  &=& '\textrm{character data}'; \\
\textrm{professor}             &=& '\textrm{character data}'; \\
\textrm{optional student list} &=& \textrm{student list} | ; \\
\textrm{student list}          &=& \textrm{student}, \textrm{student list}; \\
\textrm{optional assistant}    &=& \textrm{assistant} | ; \\
\textrm{assistant}             &=& '\textrm{character data}';
\end{eqnarray}

\section{Number 5: Exercise 5.4.1}

Show, using the string aab, that the following is ambiguous:
\begin{equation}
S \rightarrow \textrm{a}S | \textrm{a}S\textrm{b}S | \epsilon
\end{equation}

\begin{enumerate}

\item Using parse trees in Figure~\ref{5.4.1.a-1} and
  Figure~\ref{5.4.1.a-2}

\begin{figure}
\input{5.4.1.a-1.tex}
\caption{A possible parse tree for aab}\label{5.4.1.a-1}
\end{figure}

\begin{figure}
\input{5.4.1.a-2.tex}
\caption{A possible parse tree for aab}\label{5.4.1.a-2}
\end{figure}

\item Using leftmost derivations in Table~\ref{5.4.1.b}

\begin{table}
\begin{tabular}{c || c }
Derivation One & Derivation Two \\
\hline\hline
$S$                               & $S$ \\
$\textrm{a}S$                     & $\textrm{a}S\textrm{b}S$ \\
$\textrm{aa}S\textrm{b}S$         & $\textrm{aa}S\textrm{b}S$ \\
$\textrm{aa}\epsilon\textrm{b}S$  & $\textrm{aa}\epsilon\textrm{b}S$ \\
$\textrm{aab}\epsilon$            & $\textrm{aab}\epsilon$ \\
$\textrm{aab}$                    & $\textrm{aab}$
\end{tabular}
\caption{Different leftmost derivations for aab}\label{5.4.1.b}
\end{table}

\item Using rightmost derivations in Table~\ref{5.4.1.c}

\begin{table}
\begin{tabular}{c || c }
Derivation One & Derivation Two \\
\hline\hline
$S$                               & $S$ \\
$\textrm{a}S$                     & $\textrm{a}S\textrm{b}S$ \\
$\textrm{aa}S\textrm{b}S$         & $\textrm{aa}S\textrm{b}S$ \\
$\textrm{aa}S\textrm{b}\epsilon$  & $\textrm{aa}S\textrm{b}\epsilon$ \\
$\textrm{aa}\epsilon\textrm{b}$   & $\textrm{aa}\epsilon\textrm{b}$ \\
$\textrm{aab}$                    & $\textrm{aab}$
\end{tabular}
\caption{Different rightmost derivations for aab}\label{5.4.1.c}
\end{table}

\end{enumerate}

\section{Number 6: Exercise 5.4.7.a}

Usng the string +*-xyxy and the grammar:
\begin{equation}
E \rightarrow +EE | *EE | -EE | \textrm{x} | \textrm{y}
\end{equation}

\begin{enumerate}

\item Find the leftmost derivation in Table~\ref{5.4.7.a-1}
\begin{table}
\begin{tabular}{c}
$E$ \\
$+EE$ \\
$+*EEE$ \\
$+*-EEEE$ \\
$+*-\textrm{x}EEE$ \\
$+*-\textrm{xy}EE$ \\
$+*-\textrm{xyx}E$ \\
$+*-\textrm{xyxy}$
\end{tabular}
\caption{Leftmost derivation for +*-xyxy}\label{5.4.7.a-1}
\end{table}

\item Find the rightmost derivation in Table~\ref{5.4.7.a-2}
\begin{table}
\begin{tabular}{c}
$E$ \\
$+EE$ \\
$+E\textrm{y}$ \\
$+*EE\textrm{y}$ \\
$+*E\textrm{xy}$ \\
$+*-EE\textrm{xy}$ \\
$+*-E\textrm{yxy}$ \\
$+*-\textrm{xyxy}$
\end{tabular}
\caption{Rightmost derivation for +*-xyxy}\label{5.4.7.a-2}
\end{table}

\item Derivation tree in Figure~\ref{5.4.7.a-3}

\begin{figure}
\input{5.4.7.a-3.tex}
\caption{Derivation tree for +*-xyxy}\label{5.4.7.a-3}
\end{figure}

\end{enumerate}

\end{document}
