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

%

% $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 context van het aantonen dat voor elke $k > 0$ de $L(k+1)$ talen

niet de $L(k)$ talen zijn. \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 \epsilon \\

B \rightarrow b^{k-1}d \\

\end{array}

\end{equation*}





\section{Opgave 5.14}

Laat $G$ een LR(0) grammatica zijn met $A \rightarrow \alpha \bullet, \alpha

\ne \epsilon$, welke geldig is voor een levensvatbare prefix $\gamma$ er geen

enkel ander \emph{item} kan geldig zijn voor $\gamma$. Als er een \emph{item}

van de vorm $A \rightarrow \alpha B$ is levert dit een shift-reduce error op.

Als er een \emph{item} van de vorm $A \rightarrow \beta \bullet : \alpha \ne

\beta$ zal het betekenen dat er een \emph{item} 'vooraf' aan gegaan $A

\rightarrow \bullet \alpha$ \underline{en} $A \rightarrow \bullet \beta$, wat

niet mogelijk is omdat enkel de eerste geldig kan zijn per definitie.





\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}