Index: /liacs/TPFL2010/assignment3/cyk.py
===================================================================
--- /liacs/TPFL2010/assignment3/cyk.py	(revision 252)
+++ /liacs/TPFL2010/assignment3/cyk.py	(revision 253)
@@ -3,4 +3,5 @@
 # Very nasty hacks to make python algoritm look similar to pg.142 CYK algoritm.
 #
+from pprint import pprint
 
 
@@ -22,12 +23,25 @@
 n = len(w)
 r = [[[]]*(n+1) for x in irange(0,n)]
+cyk = dict();
 
 
+for k in cnf.keys():
+  for i in irange(1,n):
+    for j in irange(1,n):
+      cyk[(k,i,j)] = []
 
 
-def printr():
+def print_r():
+  print '''
+\\begin{table}[htbp] 
+\\center
+\\begin{tabular}{|c||%s}
+\\hline
+''' % ('c|'*n)
   print 'i\\textbackslash j &',
   for i in irange(1,n):
-    print "%-10s &" % i,
+    print "%-10s" % i,
+    if i != n:
+      print "&",
   print "\\\\ \\hline \\hline"
   
@@ -37,9 +51,26 @@
     for j in irange(1,n):
       if r[i][j] == [None]:
-        item = "@"
-      else:
-        item = ",".join(r[i][j]),
-      print "%-10s &" % item,
+        item = "$\\emptyset$",
+      else: 
+        item = ''
+        for k in r[i][j]:
+           c =  from_cyk(k,i,j)
+           if c:
+             item += "%s: %s \\\\" % (k, c)
+           else:
+             item += "%s \\\\" % k
+             
+      print "\\begin{tabular}{l}",
+      print "%-10s \\end{tabular}" % item,
+      if j != n:
+        print "&",
     print "\\\\ \\hline"
+  print '''
+\\end{tabular}
+\\label{tb:cyk}
+\\caption{$CYK(L(G),babbbab)$. Algoritme in \cite{JS2009}[pg.~142]}
+\\end{table}
+'''
+
 
 def to_r(i,j,k):
@@ -52,4 +83,15 @@
 def from_r(i,j):
   return r[i][j]
+
+def to_cyk(A,i,j,B):
+  cyk[(A,i,j)] += [B]
+
+def from_cyk(A,i,j):
+  r = cyk[(A,i,j)]
+  if not r:
+    return None 
+  else:
+    return ",".join([str(x) for x in r])
+
 
 def letter(i):
@@ -74,5 +116,7 @@
           if x[0] in from_r(i,k) and x[1] in from_r(k+1,j):
             to_r(i,j,y)
+	    to_cyk(y,i,j,(x[0],x[1],k))
 
 
-printr()
+print_r()
+#pprint(cyk)
Index: /liacs/TPFL2010/assignment3/report.tex
===================================================================
--- /liacs/TPFL2010/assignment3/report.tex	(revision 252)
+++ /liacs/TPFL2010/assignment3/report.tex	(revision 253)
@@ -36,15 +36,45 @@
 \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. De opgaven zijn
-willekeurig gekozen met behulp van een kans generator, het kan dus zijn dat
-niet alle onderwerpen van hoofdstuk 4 behandeld worden.
+(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{table}[htbp] 
+\center
+\begin{tabular}{|c||c|c|c|c|c|}
+\hline
+
+i\textbackslash j & 1          & 2          & 3          & 4          & 5          \\ \hline \hline
+                1 & \begin{tabular}{l} C \\       \end{tabular} & \begin{tabular}{l} $\emptyset$ \end{tabular} & \begin{tabular}{l} A: ('C', 'B', 1) \\ \end{tabular} & \begin{tabular}{l} A: ('A', 'A', 3) \\ \end{tabular} & \begin{tabular}{l} S: ('A', 'B', 3),('A', 'B', 4) \\B: ('A', 'S', 3),('A', 'S', 4) \\ \end{tabular} \\ \hline
+                2 & \begin{tabular}{l}            \end{tabular} & \begin{tabular}{l} A \\       \end{tabular} & \begin{tabular}{l} S: ('A', 'B', 2) \\B: ('A', 'S', 2) \\ \end{tabular} & \begin{tabular}{l} $\emptyset$ \end{tabular} & \begin{tabular}{l} C: ('B', '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} $\emptyset$ \end{tabular} & \begin{tabular}{l} C: ('B', 'S', 3) \\ \end{tabular} \\ \hline
+                4 & \begin{tabular}{l}            \end{tabular} & \begin{tabular}{l}            \end{tabular} & \begin{tabular}{l}            \end{tabular} & \begin{tabular}{l} A \\       \end{tabular} & \begin{tabular}{l} S: ('A', 'B', 4) \\B: ('A', 'S', 4) \\ \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} \\ \hline
+
+\end{tabular}
+\label{tb:cyk}
+\caption{$CYK(L(G),babbbab)$. Algoritme in \cite{JS2009}[pg.~142]}
+\end{table}
 
 \section{Opgave 5.5}
