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

%
% $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}
Laat $G$ een \emph{CFG} zijn zonder 'nutteloze symbolen. Als $G$ een LL(1) grammatica is dan en slechts als, voor willekeurig twee ongelijke producties van de vorm $X \rightarrow \alpha$ en $X \rightarrow \beta$, dan is het volgende geldig, als $x,y \in FOLLOW(X)$ dan $FIRST(\alpha x) \cap FIRST(\beta y) = \emptyset$. De symbolen $x$ en $y$ hoeven niet unique te zijn.

$\Rightarrow$ Als $G$ LL(1) dan moet met behulp van '{e}'{e} symbool de juiste
transitie gekozen worden. Als we bijvoorbeeld in toestand $X$ zijn dan moet
onze volgende stap (de $FIRST$) unique \footnote{De eigenschap wordt
afgedwongen door Stelling 5.3.4 en de bovenstaande definitie op
\cite{JS2009}[pg.~157]} zijn onafhankelijk wat hier achter wordt gezet.

$\Leftarrow$ Als voor alle willekeurige $x$ en $y$ beiden in $FOLLOW(X)$ beiden
geen gemeenschapelijke start symbool hebben ($FIRST(\alpha x) \cap FIRST(\beta
y) = \emptyset$), betekend dat de transities $X \rightarrow \alpha$ en $X
\rightarrow \beta$ door elkaar te onderscheiden zijn door het eerste symbool.
Omdat dit geldt voor alle transities is de taal dus herkenbaar door enkel het
eerste symbool in de transities en dus LL(1). Als ze wel een gemeenschapelijk
start symbool hebben zijn er minimaal 2 symbolen nodig om de taal te herkennen
en is deze \underline{niet} LL(1).


% \section{Opgave 5.8}
% Een voorbeeld van een LR(0) grammatica waar er een levensvatbare prefix
% $\gamma$ bestaat en \emph{item}\footnote{Ik kan geen goede vertaling voor item
% vinden welke de definie \cite{JS2009}[pg.~145] eer aandoet} $A \rightarrow
% \bullet, B \rightarrow \alpha \bullet \beta$ welke beiden geldig zijn voor
% $\gamma$.
\newpage
\section{Opgave 5.10}
Een voorbeeld van een grammatica welke wel $LL(k+1)$ is maar niet $LL(k)$, is gegeven in \cite{STOC69}[pg.~174] en is de grammatica van de taal $\{a^n(b^kd|b|cc)^n : n \ge 1\}$:
\begin{equation}
\begin{array}{l}
S \rightarrow aSA \\
S \rightarrow aA \\
A \rightarrow cc \\
A \rightarrow bB \\
A \rightarrow \varepsilon \\
B \rightarrow b^{k-1}d \\
\end{array}
\end{equation}


\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.
\bibitem[STOC69]{STOC69}Rosenkrantz, D. J. and Stearns, R. E., Properties of
deterministic top down grammars, Proceedings of the first annual
ACM symposium on Theory of computing, STOC '69, Marina del Rey,
California, United States, 165--180
\end{thebibliography}
\end{document}