\documentclass[11pt]{article}

\usepackage{hevea,xspace,graphicx,paralist}

\oddsidemargin 0cm
\textwidth 17cm

\newcommand{\question}[1]{#1}
\newcommand{\answer}[1] { {\sf #1}  {\vspace{6ex}}  }
\newcommand{\ignore}[1] {}
\newcommand{\ie}{{\em i.e.},\xspace}
\begin{document}

\thispagestyle{empty}

\begin{center}
\begin{Large}
{\bf CS 3100 -- Models of Computation -- Fall 2010}\\
{\bf Notes for Lecture 15 around Assignment 6 -- 10/19/2010}
\end{Large}
\end{center}

\noindent Topics:

\begin{compactitem}
\item Reversing CFGs
\item Obtaining NFA from purely right-linear CFGs
\item Simplifying CFGs (also related to nullability discussed on Page 76)
\item Chomsky normal form
\item CFL Pumping Lemma
\item Yacc
\item CFG to PDA: see online material against L14 (``JFLAP files'')
\item PDA to CFG
\end{compactitem}

\section{Reversing CFGs}

Given a string $s$, let $s^R$ denote the reverse of $s$

Given strings $s$ and $t$, $(st)^R = t^R s^R$

Applying this recursively,

$(stu)^R$ = $(tu)^R s^R$ = $u^R t^R s^R$

This idea can be applied to CFGs:

\begin{verbatim}
S -> A B C | 0 D | E 0 | F 0 G | 0 H 2
\end{verbatim}

can be turned into an {\tt Sr} grammar as follows:

\begin{verbatim}
Sr -> Cr Br Ar | Dr 0 | 0 Er | Gr 0 Fr | 2 Hr 0
\end{verbatim}

\section{NFA from Purely right-linear}

Reversing
\begin{footnotesize}
\begin{verbatim}
S -> A 0 | B 1 | e
A -> C 1 | 0
B -> C 1 | 1
C -> 1 | C 0
\end{verbatim}
\end{footnotesize}

We obtain

\begin{footnotesize}
\begin{verbatim}
Sr -> 0 Ar | 1 Br | e
Ar -> 1 Cr | 0
Br -> 1 Cr | 1
Cr -> 1 | 0 Cr
\end{verbatim}
\end{footnotesize}

and an NFA

\begin{footnotesize}
\begin{verbatim}
ISr - 0 -> Ar
ISr - 1 -> Br
Isr - e -> F1
Ar - 1 -> Cr
Ar - 0 -> F2
Br - 1 -> Cr
Br - 1 -> F3
Cr - 1 -> F4
Cr - 0 -> Cr
\end{verbatim}
\end{footnotesize}

\section{Simplifying CFGs}

We can simplify this CFG as follows:

\begin{footnotesize}
\begin{verbatim}
S -> A | B

A -> ( W A  |  ( X C
B -> ( W B  |  ( X D

P -> 0 Q | 2

Q -> P 0 | 3

W -> ( W W  |  ( X Y
X -> ( W X  |  ( X Z

W -> )
B -> e
\end{verbatim}
\end{footnotesize}

\begin{compactitem}
\item Notice that {\tt C,D,Y,Z}
        are {\em not} generating symbols (they can never generate any
        terminal string). Hence we can eliminate production RHS using them.
\item {\tt W} and {\tt B} are generating ({\tt W -> )} and {\tt B -> e}).
\item {\tt X} is not generating. Look at {\tt X -> ( W X}. While {\tt (}
        is generating and {\tt W} is generating, {\tt X} on the RHS isn't
        generating -- we are doing a ``bottom-up marking.'' The
        same style of reasoning applies also to {\tt X -> ( X Z}.
\item Even {\tt A} is not generating!
\item While {\tt P} and {\tt Q} are generating, they are not reachable.
\end{compactitem}

\subsection{Nullability}
The algorithm for a generating non-terminal is similar to the following from Page 76 for nullable variables:
\begin{compactitem}
\item Declare all variables (non-terminals) non-nullable.
\item Repeat Go thru productions; if any has RHS empty or all entries are nullable, then mark the LHS variable nullable
\item Until there is no increase in the set of nullable variables (non-terminals).
\item[] (The book uses ``variables'' ; we often use ``non-terminals'')
\end{compactitem}

\section{Chomsky Normal Form}

\begin{compactitem}
\item Get rid of all $\varepsilon$ productions.
\item Get rid of unit productions.
\item Make productions binary.
\item Move all terminals to unit productions.
\end{compactitem}

\subsection{Derivation length}
Derivation length for a string of length $n$: $2n-1$. So we can search all derivations systematically using dynamic programming.

\subsubsection{Cocke-Kasami-Younger (CKY) parsing algorithm}
\label{sec:cky}

\index{Cocke-Kasami-Younger Algorithm}
\index{CKY algorithm}

% gotta be in chomsky normal form

The CKY parsing algorithm uses {\em dynamic programming} in a
rather elegant manner.
%--
Basically, given any string, such as {\tt 0 0 1}, and a
Chomsky normal form grammar  such as
\\
$S\;\rightarrow\; S\; T\; \;\mid\;  0$\\
$T\;\rightarrow\; S\; T\; \;\mid\;  1$,  \\
the following steps describe how we ``parse the string'' (check that
the string is a member of the language of the grammar):
%--
 \begin{list}{$\bullet$}{\addtolength{\itemsep}{-1.6\itemsep}}
 \item Consider {\em all possible} substrings of the given string
        of length 1, and determine all non-terminals which can generate them.
 \item Now, consider {\em all possible} substrings of the given string
        of length 2, and determine all pairs of
        non-terminals in juxtaposition which can generate them.
 \item Repeat this for strings of lengths 3, 4, $\ldots$, until the
        full length of the string has been examined.
 \end{list}
%--
\begin{footnotesize}
\begin{verbatim}
Given string: 001

 0 0 1
^ ^ ^ ^
| | | |
0 1 2 3 are the positions in the string. See who (which non-terminals) can 
generate these positions.

Attempt to span position 0 thru 3.

0         0               0                 0
a 1       {S} 1           {S} 1             {S}    1
b c 2     b   {S} 2       {}  {S}   2       {}    {S}   2
d e f 3   d    e  {T} 3   d   {S,T} {T} 3   {S,T} {S,T} {T} 3

{S} can yield posn 0--1 and {S,T} can yield posn 1--3. 

The concat of {S} and {S,T} is {SS, ST}.

Both S and T can yield ST. Neither can yield SS. Thus we mark the "1,3" "0,3" positions with {S,T}.

We can now say that S can generate the string from position 0 thru 3. Hence parsed!
\end{verbatim}
\end{footnotesize}
%--

\section{The CFL Pumping Lemma}

Basic idea: Very long string needs very tall parse tree; therefore some non-terminal along the path repeats.
Can do ``switharoo'' of non-terminals to pump trees!

Given any CFG $G = (N,\Sigma,P,S)$, there exists a number $p$
such that given a string $w$ in $L(G)$ such that $|w|\geq p$,
we can split $w$ into $w=uvxyz$ such that $|vy|>0$ {(\sl one of $v$ or $y$ is non-empty)},
$|vxy|\leq p$, and for every $i\ge 0$, $uv^i x y^i z \in L(G)$.


\begin{footnotesize}
\begin{verbatim}
S -> ( S ) | T | e

T -> [ T ] | T T | e.
\end{verbatim}
\end{footnotesize}

Here is an example derivation:
%--
\begin{footnotesize}
\begin{verbatim}
S => ( S ) => (( T )) => (( [ T ] )) => (( [  ] ))
                 ^            ^
               Occurrence-1   Occurrence-2

Occurrence-1 involves Derivation-1: T => [ T ] => [ ]
Occurrence-2 involves Derivation-2: T => e
\end{verbatim}
\end{footnotesize}

Here, the second {\tt T} arises because we took {\tt T} and
expanded it into \\ {\tt [ T ]} and then to {\tt [  ]}.

Now, the basic idea is that we can use Derivation-1 used in the
first occurrence in place of Derivation-2, to obtain a longer string:

\begin{footnotesize}
\begin{verbatim}
S => (S) => ((T))  => (( [ T ] )) => (( [[ T ]] )) => (( [[ ]] ))
              ^            ^
              Occurrence-1 Use Derivation-1 here
\end{verbatim}
\end{footnotesize}

In the same fashion, we can use Derivation-2 in place of Derivation-1 to obtain
a shorter string, as well:
%--
\begin{footnotesize}
\begin{verbatim}
S => ( S ) => ( ( T ) ) => ( ( ) )
                  ^
                  Use Derivation-2 here
\end{verbatim}
\end{footnotesize}








\end{document}
