Changeset 255 for liacs/TPFL2010


Ignore:
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:
3 edited

Legend:

Unmodified
Added
Removed

  • liacs/TPFL2010/assignment3/cyk.py

    r254 r255  
    1616  }
    1717
    18 w = 'babbab'
     18w = 'babbbab'
    1919cnf = {
    2020  'S' : ['AB','b'],
    … …  
    6262        item = ''
    6363        for k in r[i][j]:
    64            c =  from_cyk(k,i,j)
     64           c = from_cyk(k,i,j)
    6565           if c:
    6666             item += "%s: %s \\\\" % (k, c)
    … …  
    7575  print '''
    7676\\end{tabular}
    77 \\caption{$CYK(L(G),%s)$. Algoritme in \cite{JS2009}[pg.~142]}
     77\\caption{$CYK(L(G),%s)$. Algoritme beschreven in \cite{JS2009}[pg.~142]}
    7878\\end{table}
    7979''' % w

  • liacs/TPFL2010/assignment3/report.tex

    r254 r255  
    5858Gebruikmakend van het CYK algoritme gaan we aantonen dat $x = babbbab \in L(G)$
    5959zit. De ondersteunende tabel is van de grootte $6\times6$ omdat dit de lengte
    60 van het woord $x$ is. In tabel~\ref{tb:cyk} staat cel $i,j$ voor welke
    61 transities er gevolgt moet worden om het subwoord $x[i..j]$ te vormen.
     60van het woord $x$ is. In tabel~\ref{tb:opdr1} staat\footnote{Om de \LaTeX~tabel
     61automatisch te gegenereren vanuit een woord en een CFG gramatica heb ik
     62\url{http://rickvanderzwet.nl/svn/personal/liacs/TPFL2010/assignment3/cyk.py}
     63geschreven, vanwege de fouten ik met handwerk maakte.} cel $i,j$ voor welke
     64transities er gevolgt moet worden om het
     65subwoord $x[i..j]$ te vormen. Omdat de start transitie $S$ in $1,6$ staat zit
     66het woord $x$ in $L(G)$. De ontleedboom is te zien in figuur~\ref{fig:opdr1}.
    6267
    6368
    6469\begin{sidewaystable}[htbp]
    6570\center
    66 \begin{tabular}{|c||c|c|c|c|c|c|}
     71\begin{tabular}{|c||c|c|c|c|c|c|c|}
    6772\hline
    68 
    69 i\textbackslash j & 1          & 2          & 3          & 4          & 5          & 6          \\ \hline \hline
    70                 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
    71                 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
    72                 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
    73                 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
    74                 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
    75                 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
     73i\textbackslash j & 1          & 2          & 3          & 4          & 5          & 6          & 7          \\ \hline \hline
     74                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
     75                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
     76                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
     77                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
     78                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
     79                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
     80                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
    7681
    7782\end{tabular}
    78 \caption{$CYK(L(G),a)$. Algoritme in \cite{JS2009}[pg.~142]}
     83\caption{$CYK(L(G),a)$. Algoritme beschreven in \cite{JS2009}[pg.~142]}
     84\label{tb:opdr1}
    7985\end{sidewaystable}
     86
     87\begin{figure}
     88\center
     89\begin{tikzpicture}
     90  [level distance=10mm,level/.style={sibling distance=40mm/#1}]
     91  \node {S}
     92     child {node {A}
     93       child {node {B}
     94         child {node {b}}
     95       }
     96       child {node {C}
     97         child {node {a}}
     98       }
     99     }
     100     child {node {B}
     101       child {node {C}
     102         child {node {S}
     103           child {node {S}
     104             child {node {b}
     105             }
     106           }
     107           child {node {S}
     108             child {node {b}}
     109           }
     110         }
     111         child {node {S}
     112           child {node {b}}
     113         }
     114       }
     115       child {node {B}
     116         child {node {A}
     117           child {node {a}}
     118         }
     119         child {node {S}
     120           child {node {b}}
     121         }
     122       }
     123     }
     124  ;
     125\end{tikzpicture}
     126\label{fig:opdr1}
     127\caption{Ontleedboom voor het woord $babbbab$}
     128\end{figure}
    80129
    81130\section{Opgave 5.5}
Note: See TracChangeset for help on using the changeset viewer.