% % $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{}} \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}