1 \documentclass{article}

     2 \usepackage{charter}

     3 \usepackage{hyperref}

     4 \usepackage{amssymb}

     5 \usepackage{amsmath}

     6 \usepackage{tikz}

     7 \usetikzlibrary{automata}

     8 

     9 \newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions

    10 

    11 \begin{document}

    12 

    13 \noindent

    14 {\bf \underline{Non-exhaustive} list of topics you should know for the exam!}

    15 

    16 \section{Sets}

    17 

    18 \begin{itemize}

    19 \item What is a language?

    20 \item concatenation of two sets of string

    21 \item power of a set of strings

    22 \end{itemize}

    23 

    24 \section{Regular Expressions}

    25 

    26 \begin{itemize}

    27 \item What is the language of a regular expression?

    28 \item When are two regular expressions are equal?

    29 \item {\it nullable}, {\it der}, {\it zeroable}, {\it rev}

    30 \item induction principle of regular expressions

    31 \item tokens, maximal munch rule

    32 \item ``negative'' regular expression 

    33 \item tokenisation

    34 \end{itemize}

    35 

    36 \section{Automata}

    37 

    38 \begin{itemize}

    39 \item DFA, NFA

    40 \item What is the language recognised by a DFA?

    41 \item Reg $\rightarrow$ NFA

    42 \item NFA $\rightarrow$ DFA (subset construction)

    43 \item DFA minimisation (Hopcroft's algorithm)

    44 \item complement DFA 

    45 \item completion of an automaton

    46 \item DFA $\rightarrow$ Reg (Brzozowsky's algorithm, equational systems, Arden's lemma)

    47 \end{itemize}

    48 

    49 \section{Grammars}

    50 

    51 \begin{itemize}

    52 \item ambiguous grammars 

    53 \item parse trees

    54 \item ASTs

    55 \item CYK algorithm

    56 \end{itemize}

    57 

    58 \end{document}

    59 

    60 %%% Local Variables: 

    61 %%% mode: latex

    62 %%% TeX-master: t

    63 %%% End: