\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 strings
\item power of a set of strings
\end{itemize}

\section{Regular Expressions}

\begin{itemize}
\item definition of regular expressions
\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 regular expression for complement language 
\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: