# HG changeset patch # User Christian Urban # Date 1352654891 0 # Node ID b64e876832cc7ee06c45d5229773ec376fa97e6c # Parent f516892da4703506f7148ed09783c534c246dfda added diff -r f516892da470 -r b64e876832cc hw07.pdf Binary file hw07.pdf has changed diff -r f516892da470 -r b64e876832cc hw07.tex --- /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: diff -r f516892da470 -r b64e876832cc re1.scala --- 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)) } diff -r f516892da470 -r b64e876832cc re2.scala --- 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)) } diff -r f516892da470 -r b64e876832cc re3.scala --- 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))) } diff -r f516892da470 -r b64e876832cc slides06.pdf Binary file slides06.pdf has changed diff -r f516892da470 -r b64e876832cc topics.pdf Binary file topics.pdf has changed diff -r f516892da470 -r b64e876832cc topics.tex --- /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: