Changeset 255 for liacs/TPFL2010/assignment3

Timestamp:

Dec 16, 2010, 8:38:30 PM (14 years ago)

Author:

Rick van der Zwet

Message:

_eindelijk_ opdr1 af.

Location:

liacs/TPFL2010/assignment3

Files:

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

liacs/TPFL2010/assignment3/cyk.py

@@ -16 +16 @@
   }
 
-w = 'babbab'
+w = 'babbbab'
 cnf = {
   'S' : ['AB','b'],
@@ -62 +62 @@
         item = ''
         for k in r[i][j]:
-           c =  from_cyk(k,i,j)
+           c = from_cyk(k,i,j)
            if c:
              item += "%s: %s \\\\" % (k, c)
@@ -75 +75 @@
   print '''
 \\end{tabular}
-\\caption{$CYK(L(G),%s)$. Algoritme in \cite{JS2009}[pg.~142]}
+\\caption{$CYK(L(G),%s)$. Algoritme beschreven in \cite{JS2009}[pg.~142]}
 \\end{table}
 ''' % w

liacs/TPFL2010/assignment3/report.tex

@@ -58 +58 @@
 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.
+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 gramatica 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|}
+\begin{tabular}{|c||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
+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 in \cite{JS2009}[pg.~142]}
+\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}