
diff -r 4758a6155878 -r 1ab41c59e3d3 hw/hw07.tex
--- a/hw/hw07.tex	Thu Sep 26 10:39:23 2013 +0100
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,75 +0,0 @@
-\documentclass{article}
-\usepackage{charter}
-\usepackage{hyperref}
-\usepackage{amssymb}
-\usepackage{amsmath}
-\usepackage{tikz}
-\usetikzlibrary{automata}
-
-\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions
-
-\begin{document}
-
-\section*{Homework 7}
-
-\begin{enumerate}
-\item Suppose the following finite deterministic automaton over the alphabet $\{0, 1\}$.
-
-\begin{center}
-\begin{tikzpicture}[scale=2, line width=0.5mm]
-  \node[state, initial, accepting]        (q0) at ( 0,1) {$q_0$};
-  \node[state, accepting]                    (q1) at ( 1,1) {$q_1$};
- \node[state] (q2) at ( 2,1) {$q_2$};
-  \path[->] (q0) edge[bend left] node[above] {$0$} (q1)
-                  (q1) edge[bend left] node[above] {$1$} (q0)
-                  (q2) edge[bend left=50] node[below] {$1$} (q0)
-                  (q1) edge node[above] {$0$} (q2)
-                  (q2) edge [loop right] node {$0$} ()
-                  (q0) edge [loop below] node {$1$} ()
-            ;
-\end{tikzpicture}
-\end{center}
-
-Give a regular expression that can recognise the same language as
-this automaton. (Hint: If you use Brzozwski's method, you can assume
-Arden's lemma which states that an equation of the form $q = q\cdot r + s$
-has the unique solution $q = s \cdot r^*$.)
-
-\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}
-
-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
-by the grammar:
-
-\begin{center}
-\texttt{The trainer trains the student team}
-\end{center}
-
-\item {\bf (Optional)} The task is to match strings where the letters are in alphabetical order---for example, 
-\texttt{abcfjz} would pass, but \texttt{acb} would not. Whitespace should be ignored---for example
-\texttt{ab c d} should pass. The point is to try to get the regular expression as short as possible!
-See:
-
-\begin{center}
-\url{http://callumacrae.github.com/regex-tuesday/challenge11.html}
-\end{center}
-\end{enumerate}
-
-\end{document}
-
-%%% Local Variables: 
-%%% mode: latex
-%%% TeX-master: t
-%%% End: 




