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