Binary file hw07.pdf has changed

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/hw07.tex	Sun Nov 11 17:28:11 2012 +0000
@@ -0,0 +1,68 @@
+\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}
+
+
+\end{enumerate}
+
+\end{document}
+
+%%% Local Variables: 
+%%% mode: latex
+%%% TeX-master: t
+%%% End: 

--- a/re1.scala	Mon Nov 05 20:31:58 2012 +0000
+++ b/re1.scala	Sun Nov 11 17:28:11 2012 +0000
@@ -55,7 +55,7 @@
 
 //n-times
 def NTIMES(r: Rexp, n: Int) : Rexp = n match {
-  case 0 => NULL
+  case 0 => EMPTY
   case 1 => r
   case n => SEQ(r, NTIMES(r, n - 1))
 }

--- a/re2.scala	Mon Nov 05 20:31:58 2012 +0000
+++ b/re2.scala	Sun Nov 11 17:28:11 2012 +0000
@@ -79,7 +79,7 @@
 
 //n-times
 def NTIMES(r: Rexp, n: Int) : Rexp = n match {
-  case 0 => NULL
+  case 0 => EMPTY
   case 1 => r
   case n => SEQ(r, NTIMES(r, n - 1))
 }

--- a/re3.scala	Mon Nov 05 20:31:58 2012 +0000
+++ b/re3.scala	Sun Nov 11 17:28:11 2012 +0000
@@ -32,11 +32,12 @@
   }
 }
 case class NTIMES(r: Rexp, n: Int) extends Rexp {
-  override def simp = r.simp match {
-    case NULL => NULL
-    case EMPTY => EMPTY
-    case r => NTIMES(r, n)
-  }
+  override def simp = if (n == 0) EMPTY else 
+    r.simp match {
+      case NULL => NULL
+      case EMPTY => EMPTY
+      case r => NTIMES(r, n)
+    }
 }
 
 // some convenience for typing in regular expressions
@@ -57,7 +58,7 @@
   case ALT(r1, r2) => nullable(r1) || nullable(r2)
   case SEQ(r1, r2) => nullable(r1) && nullable(r2)
   case STAR(_) => true
-  case NTIMES(r, i) => if (i == 0) false else nullable(r)
+  case NTIMES(r, i) => if (i == 0) true else nullable(r)
 }
 
 // derivative of a regular expression w.r.t. a character
@@ -88,13 +89,6 @@
 //one or zero
 def OPT(r: Rexp) = ALT(r, EMPTY)
 
-//n-times
-/*def NTIMES(r: Rexp, n: Int) : Rexp = n match {
-  case 0 => NULL
-  case 1 => r
-  case n => SEQ(r, NTIMES(r, n - 1))
-}*/
-
 def RTEST(n: Int) = SEQ(NTIMES(OPT("a"), n), NTIMES("a", n))
 
 def time_needed[T](i: Int, code: => T) = {
@@ -105,8 +99,8 @@
 }
 
 
-for (i <- 1 to 10001 by 500) {
-  println(i + " " + time_needed(1, matcher(RTEST(i), "a" * i)))
+for (i <- 1 to 11001 by 500) {
+  println(i + " " + + " " + time_needed(1, matcher(RTEST(i), "a" * i)))
 }
 
 

Binary file slides06.pdf has changed

Binary file topics.pdf has changed

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/topics.tex	Sun Nov 11 17:28:11 2012 +0000
@@ -0,0 +1,63 @@
+\documentclass{article}
+\usepackage{charter}
+\usepackage{hyperref}
+\usepackage{amssymb}
+\usepackage{amsmath}
+\usepackage{tikz}
+\usetikzlibrary{automata}
+
+\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions
+
+\begin{document}
+
+\noindent
+{\bf \underline{Non-exhaustive} list of topics you should know for the exam!}
+
+\section{Sets}
+
+\begin{itemize}
+\item What is a language?
+\item concatenation of two sets of string
+\item power of a set of strings
+\end{itemize}
+
+\section{Regular Expressions}
+
+\begin{itemize}
+\item What is the language of a regular expression?
+\item When are two regular expressions are equal?
+\item {\it nullable}, {\it der}, {\it zeroable}, {\it rev}
+\item induction principle of regular expressions
+\item tokens, maximal munch rule
+\item ``negative'' regular expression 
+\item tokenisation
+\end{itemize}
+
+\section{Automata}
+
+\begin{itemize}
+\item DFA, NFA
+\item What is the language recognised by a DFA?
+\item Reg $\rightarrow$ NFA
+\item NFA $\rightarrow$ DFA (subset construction)
+\item DFA minimisation (Hopcroft's algorithm)
+\item complement DFA 
+\item completion of an automaton
+\item DFA $\rightarrow$ Reg (Brzozowsky's algorithm, equational systems, Arden's lemma)
+\end{itemize}
+
+\section{Grammars}
+
+\begin{itemize}
+\item ambiguous grammars 
+\item parse trees
+\item ASTs
+\item CYK algorithm
+\end{itemize}
+
+\end{document}
+
+%%% Local Variables: 
+%%% mode: latex
+%%% TeX-master: t
+%%% End: