source: liacs/TPFL2010/assignment3/report.tex@ 257

%
% $Id: report.tex 571 2008-04-20 17:31:04Z rick $
%

\documentclass[12pt,a4paper]{article}

\frenchspacing
\usepackage[english,dutch]{babel}
\selectlanguage{dutch}
\usepackage[pdftex]{graphicx}
\usepackage{url}
\usepackage{amssymb,amsmath}
\usepackage{float}
\usepackage{tikz}
\usepackage{fixltx2e}
\usepackage{rotating}

\usetikzlibrary{arrows,decorations.pathmorphing,backgrounds,positioning,fit,petri}



\setlength\parindent{0pt}
\setlength\parskip{\baselineskip}
\floatstyle{ruled}
\newfloat{algoritm}{thp}{lop}
\floatname{algoritm}{Algoritme}

\title{Opdracht 3 \\
\large{Topics on Parsing and Formal Languages - fall 2010}}
\author{Rick van der Zwet\\
  \texttt{<hvdzwet@liacs.nl>}}
\date{\today}


\begin{document}
\newcommand{\DFA}{\emph{DFA}~}
\newcommand{\qed}{\hfill \ensuremath{\Box}}
\newcommand{\all}{\Sigma^*}
\newcommand{\sep}{~|~}
\maketitle
\begin{abstract}
Dit schrijven zal uitwerkingen van opgaven behandelen uit het boek
\cite{JS2009} gebruikt bij het college. In deze opdracht zullen vijf opgaven
(1, 5, 6, 8, 14) van hoofdstuk 5 behandeld worden.
\end{abstract}

\section{Opgave 5.1}
De grammatica $G$ bestaat uit de volgende producties:
\begin{equation*}
\begin{array}{l}
S \rightarrow AB \sep b \\
A \rightarrow BC \sep a \\
B \rightarrow AS \sep CB \sep b \\
C \rightarrow SS \sep a  \\
\end{array}
\end{equation*}

Gebruikmakend van het CYK algoritme gaan we aantonen dat $x = babbbab \in L(G)$
zit. De ondersteunende tabel is van de grootte $6\times6$ omdat dit de lengte
van het woord $x$ is. In tabel~\ref{tb:opdr1} staat\footnote{Om de \LaTeX~tabel 
automatisch te gegenereren vanuit een woord en een CFG grammatica heb ik
\url{http://rickvanderzwet.nl/svn/personal/liacs/TPFL2010/assignment3/cyk.py}
geschreven, vanwege de fouten ik met handwerk maakte.} cel $i,j$ voor welke
transities er gevolgt moet worden om het
subwoord $x[i..j]$ te vormen. Omdat de start transitie $S$ in $1,6$ staat zit
het woord $x$ in $L(G)$. De ontleedboom is te zien in figuur~\ref{fig:opdr1}. 


\begin{sidewaystable}[htbp] 
\center
\begin{tabular}{|c||c|c|c|c|c|c|c|}
\hline
i\textbackslash j & 1          & 2          & 3          & 4          & 5          & 6          & 7          \\ \hline \hline
                1 & \begin{tabular}{l} S \\B \\   \end{tabular} & \begin{tabular}{l} A: (B,C,1) \\ \end{tabular} & \begin{tabular}{l} C: (S,S,1) \\S: (A,B,2) \\B: (A,S,2) \\ \end{tabular} & \begin{tabular}{l} A: (B,C,1) \\B: (C,B,3) \\C: (S,S,3) \\ \end{tabular} & \begin{tabular}{l} C: (S,S,1) \\S: (A,B,2),(A,B,4) \\A: (B,C,3) \\B: (A,S,4),(C,B,4) \\ \end{tabular} & \begin{tabular}{l} A: (B,C,5) \\ \end{tabular} & \begin{tabular}{l} A: (B,C,1),(B,C,3),(B,C,4) \\C: (S,S,1),(S,S,5) \\S: (A,B,2),(A,B,4)\\...(A,B,5),(A,B,6) \\B: (A,S,2),(C,B,3)\\...(A,S,4),(C,B,4),(A,S,5)\\...(C,B,5),(A,S,6) \\ \end{tabular} \\ \hline
                2 & \begin{tabular}{l}            \end{tabular} & \begin{tabular}{l} A \\C \\   \end{tabular} & \begin{tabular}{l} S: (A,B,2) \\B: (A,S,2),(C,B,2) \\ \end{tabular} & \begin{tabular}{l} C: (S,S,3) \\ \end{tabular} & \begin{tabular}{l} S: (A,B,2) \\B: (C,B,2),(C,B,4) \\A: (B,C,3) \\ \end{tabular} & \begin{tabular}{l} A: (B,C,5) \\ \end{tabular} & \begin{tabular}{l} S: (A,B,2),(A,B,5),(A,B,6) \\B: (A,S,2),(C,B,2),\\...(C,B,4),(A,S,5),(A,S,6) \\A: (B,C,3) \\C: (S,S,5) \\ \end{tabular} \\ \hline
                3 & \begin{tabular}{l}            \end{tabular} & \begin{tabular}{l}            \end{tabular} & \begin{tabular}{l} S \\B \\   \end{tabular} & \begin{tabular}{l} C: (S,S,3) \\ \end{tabular} & \begin{tabular}{l} A: (B,C,3) \\B: (C,B,4) \\ \end{tabular} & \begin{tabular}{l} A: (B,C,5) \\ \end{tabular} & \begin{tabular}{l} A: (B,C,3) \\B: (C,B,4),(A,S,5),(A,S,6) \\S: (A,B,5),(A,B,6) \\ \end{tabular} \\ \hline
                4 & \begin{tabular}{l}            \end{tabular} & \begin{tabular}{l}            \end{tabular} & \begin{tabular}{l}            \end{tabular} & \begin{tabular}{l} S \\B \\   \end{tabular} & \begin{tabular}{l} C: (S,S,4) \\ \end{tabular} & \begin{tabular}{l} $\emptyset$ \end{tabular} & \begin{tabular}{l} A: (B,C,4) \\C: (S,S,4) \\B: (C,B,5) \\ \end{tabular} \\ \hline
                5 & \begin{tabular}{l}            \end{tabular} & \begin{tabular}{l}            \end{tabular} & \begin{tabular}{l}            \end{tabular} & \begin{tabular}{l}            \end{tabular} & \begin{tabular}{l} S \\B \\   \end{tabular} & \begin{tabular}{l} A: (B,C,5) \\ \end{tabular} & \begin{tabular}{l} C: (S,S,5) \\S: (A,B,6) \\B: (A,S,6) \\ \end{tabular} \\ \hline
                6 & \begin{tabular}{l}            \end{tabular} & \begin{tabular}{l}            \end{tabular} & \begin{tabular}{l}            \end{tabular} & \begin{tabular}{l}            \end{tabular} & \begin{tabular}{l}            \end{tabular} & \begin{tabular}{l} A \\C \\   \end{tabular} & \begin{tabular}{l} S: (A,B,6) \\B: (A,S,6),(C,B,6) \\ \end{tabular} \\ \hline
                7 & \begin{tabular}{l}            \end{tabular} & \begin{tabular}{l}            \end{tabular} & \begin{tabular}{l}            \end{tabular} & \begin{tabular}{l}            \end{tabular} & \begin{tabular}{l}            \end{tabular} & \begin{tabular}{l}            \end{tabular} & \begin{tabular}{l} S \\B \\   \end{tabular} \\ \hline

\end{tabular}
\caption{$CYK(L(G),a)$. Algoritme beschreven in \cite{JS2009}[pg.~142]}
\label{tb:opdr1}
\end{sidewaystable}

\begin{figure}
\center
\begin{tikzpicture}
  [level distance=10mm,level/.style={sibling distance=40mm/#1}]
  \node {S}
     child {node {A}
       child {node {B} 
         child {node {b}}
       }
       child {node {C} 
         child {node {a}}
       }
     }
     child {node {B}
       child {node {C} 
         child {node {S}
           child {node {S}
             child {node {b}
             }
           }
           child {node {S}
             child {node {b}}
           }
         }
         child {node {S}
           child {node {b}}
         }
       }
       child {node {B}
         child {node {A}
           child {node {a}}
         }
         child {node {S}
           child {node {b}}
         }
       }
     }
  ;
\end{tikzpicture}
\label{fig:opdr1}
\caption{Ontleedboom voor het woord $babbbab$}
\end{figure}

\section{Opgave 5.5}
Om een LL(1) grammatica te generen voor alle woorden in $\{w \in
\{a,b\}^*~:~|w|_a = |w|_b\}$ is:
\begin{equation*}
S \rightarrow aSbS \sep bSaS \sep \emptyset
\end{equation*}
Om aan te tonen dat de grammatica correct is, is het eerst belangrijk om te
zien dat elke keer dat een $a$ genereerd word er ook automatisch een $b$
genereerd wordt. Deze dus altijd gelijk zijn. 
Om te laten zien dat deze grammatica \emph{alle} woorden in de taal bevat is
bewijzen we met inductie naar lengte van het woord. Als $|w| = 0$ dan is $w =
\emptyset$, deze wordt door de taal herkent.

Neem alle woorden tot lengte $2N$ en een gelijk aantal $a$ en $b$ afleidbaar
zijn van $S$. Neem nu de string $w'$ met een gelijk aantal $a$ en $b$, een
lengte van $2(N+1)$ en $a$ als begin symbool. In het slechte geval is $2N+2$
weer nieuw woord doordat je altijd een extra $T$ kan ontwikkelen en die daarna
laat terminereren. Bijvoorbeeld $abab \rightarrow abaSbS \rightarrow ababSaSbS
\rightarrow ababab$. 

In de betere gevallen bestaat er een $2 \le j \le 2N+2$ zodaning dat $j$
aangeeft dat $w[1..j]$ een gelijk aantal $a$ en $b$ heeft, zodanig dat de vorm
van $w' = aw_1bw_2$. Met inductie kunnen we bewijzen dat $w_1$ en $w_2$
gemaakt kunnen worden van $S$, wat volgt dat $w'$ ook van $S$ gemaakt kan
worden.

LL(1) eigenschap wordt bereikt, door naar de \emph{FIRST} te kijken, welke
respectivelijk $\{a\}, \{b\}, \{\emptyset\}$ zijn. De $FOLLOW(S) =
\{a,b,\emptyset\}$. Deze twee gegevens samen maken dat de LL(1) bereikt wordt,
welke ook te zijn is in tabel~\ref{tb:opdr5}.

\begin{table}
\center
\begin{tabular}{c||c|c|c}
y \textbackslash x & a & b & \$ \\ 
\hline \hline
S & $S \rightarrow aSbS$ & $S \rightarrow bSaS$ & $S \rightarrow \emptyset$ \\
a & pop & & \\
b & & pop & \\
\# & & & accept \\
\end{tabular}
\caption{Ontleedtabel for Opdracht 5.5}
\label{tb:opdr5}
\end{table}


\section{Opgave 5.6}


\section{Opgave 5.8}


\section{Opgave 5.14}


\begin{thebibliography}{1}
\bibitem[JS2009]{JS2009}Jeffrey Shallit, \emph{A second course in formal
languages and automata theory }, \emph{Cambridge University Press}, 2009.
\end{thebibliography}
\newpage
\end{document}