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

%
% $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 gramatica $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:cyk} staat cel $i,j$ voor welke
transities er gevolgt moet worden om het subwoord $x[i..j]$ te vormen.


\begin{sidewaystable}[htbp] 
\center
\begin{tabular}{|c||c|c|c|c|c|c|}
\hline

i\textbackslash j & 1          & 2          & 3          & 4          & 5          & 6          \\ \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} A: (B,C,4) \\ \end{tabular} & \begin{tabular}{l} A: (B,C,1),(B,C,3) \\C: (S,S,1),(S,S,3) \\S: (A,B,2),(A,B,4),(A,B,5) \\B: (C,B,3),(A,S,4),(C,B,4),(A,S,5) \\ \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} $\emptyset$ \end{tabular} & \begin{tabular}{l} S: (A,B,2) \\B: (C,B,2),(C,B,4) \\A: (B,C,3) \\C: (S,S,3) \\ \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} $\emptyset$ \end{tabular} & \begin{tabular}{l} A: (B,C,3) \\C: (S,S,3) \\B: (C,B,4) \\ \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} A: (B,C,4) \\ \end{tabular} & \begin{tabular}{l} C: (S,S,4) \\S: (A,B,5) \\B: (A,S,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} A \\C \\   \end{tabular} & \begin{tabular}{l} S: (A,B,5) \\B: (A,S,5),(C,B,5) \\ \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} S \\B \\   \end{tabular} \\ \hline

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

\section{Opgave 5.5}


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