Changeset 253 for liacs

Timestamp:

Dec 15, 2010, 4:42:17 PM (14 years ago)

Author:

Rick van der Zwet

Message:

Implementation of the algoritm

Location:

liacs/TPFL2010/assignment3

Files:

• cyk.py (modified) (5 diffs)
• report.pdf (modified) ( previous)
• report.tex (modified) (1 diff)

liacs/TPFL2010/assignment3/cyk.py

@@ -3 +3 @@
 # Very nasty hacks to make python algoritm look similar to pg.142 CYK algoritm.
 #
+from pprint import pprint
 
 
@@ -22 +23 @@
 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 +51 @@
     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 +83 @@
 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 +116 @@
           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)

liacs/TPFL2010/assignment3/report.tex

@@ -36 +36 @@
 \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}