# HG changeset patch
# User Christian Urban <urbanc@in.tum.de>
# Date 1573060198 0
# Node ID 7b7736bea3ca876b022db23d6af6449bb3e517d6
# Parent  eecc4d5a2172bacd23a4ab6f7d77dfa653f47000
updated

diff -r eecc4d5a2172 -r 7b7736bea3ca handouts/ho05.pdf
Binary file handouts/ho05.pdf has changed
diff -r eecc4d5a2172 -r 7b7736bea3ca handouts/ho05.tex
--- a/handouts/ho05.tex	Wed Nov 06 15:04:40 2019 +0000
+++ b/handouts/ho05.tex	Wed Nov 06 17:09:58 2019 +0000
@@ -459,7 +459,39 @@
 
 To answer the question about complexity, let me describe next the CYK
 algorithm (named after the authors Cocke–Younger–Kasami). This algorithm
-works with grammars that are in Chomsky normalform. 
+works with grammars that are in \emph{Chomsky normalform}. In Chomsky
+normalform all rules must be of the form $\meta{A} ::= a$, where $a$ is 
+a terminal, or $\meta{A} ::= \meta{B}\cdot \meta{C}$, where $\meta{B}$ and
+$\meta{B}$ need to be non-terminals. And no rule can contain $\epsilon$.
+The following grammar is in Chomsky normalform:
+
+\begin{plstx}[margin=1cm]
+  : \meta{S\/} ::= \meta{N}\cdot \meta{P}\\
+  : \meta{P\/} ::= \meta{V}\cdot \meta{N}\\
+  : \meta{N\/} ::= \meta{N}\cdot \meta{N}\\
+  : \meta{N\/} ::= \meta{A}\cdot \meta{N}\\
+  : \meta{N\/} ::= \texttt{student} | \texttt{trainer} | \texttt{team} 
+                   | \texttt{trains}\\
+  : \meta{V\/} ::= \texttt{trains} | \texttt{team}\\
+  : \meta{A\/} ::= \texttt{The} | \texttt{the}\\
+\end{plstx}
+
+\noindent
+where $\meta{S}$ is the start symbol and $\meta{S}$, $\meta{P}$,
+$\meta{N}$, $\meta{V}$ and $\meta{A}$ are non-terminals. The ``words''
+are terminals. The rough idea behind this grammar is that $\meta{S}$
+stands for a sentence, $\meta{P}$ is a predicate, $\meta{N}$ is a noun
+and so on. For example the rule \mbox{$\meta{P} ::= \meta{V}\cdot
+\meta{N}$} states that a predicate can be a verb followed by a noun.
+Now the question is whether the string 
+
+\begin{center}
+  \texttt{The trainer trains the student team}
+\end{center}
+
+\noindent
+is recognised by the grammar. The CYK algorithm starts with the
+following triangular data structure.
 
 TBD
 
diff -r eecc4d5a2172 -r 7b7736bea3ca hws/hw07.pdf
Binary file hws/hw07.pdf has changed
diff -r eecc4d5a2172 -r 7b7736bea3ca hws/hw07.tex
--- a/hws/hw07.tex	Wed Nov 06 15:04:40 2019 +0000
+++ b/hws/hw07.tex	Wed Nov 06 17:09:58 2019 +0000
@@ -1,5 +1,6 @@
 \documentclass{article}
 \usepackage{../style}
+\usepackage{../grammar}
 
 \begin{document}
 
@@ -26,17 +27,16 @@
 
 \item Consider the following grammar 
 
-\begin{center}
-\begin{tabular}{l}
-$S \rightarrow N\cdot P$\\
-$P \rightarrow V\cdot N$\\
-$N \rightarrow N\cdot N$\\
-$N \rightarrow A \cdot N$\\
-$N \rightarrow \texttt{student} \;|\; \texttt{trainer} \;|\; \texttt{team} \;|\; \texttt{trains}$\\
-$V \rightarrow \texttt{trains} \;|\; \texttt{team}$\\
-$A \rightarrow \texttt{The} \;|\; \texttt{the}$\\
-\end{tabular}
-\end{center}
+\begin{plstx}[margin=1cm]
+  : \meta{S\/} ::= \meta{N\/}\cdot \meta{P\/}\\
+  : \meta{P\/} ::= \meta{V\/}\cdot \meta{N\/}\\
+  : \meta{N\/} ::= \meta{N\/}\cdot \meta{N\/}\\
+  : \meta{N\/} ::= \meta{A\/}\cdot \meta{N\/}\\
+  : \meta{N\/} ::= \texttt{student} \mid \texttt{trainer} \mid \texttt{team} \mid \texttt{trains}\\
+  : \meta{V\/} ::= \texttt{trains} \mid \texttt{team}\\
+  : \meta{A\/} ::= \texttt{The} \mid \texttt{the}\\
+\end{plstx}
+
 
 where $S$ is the start symbol and $S$, $P$, $N$, $V$ and $A$ are non-terminals.
 Using the CYK-algorithm, check whether or not the following string can be parsed