--- /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: