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