\begin{frame}{Minimising of NFAs} Minimising of NFAs is very difficult. \begin{example} \begin{center} \begin{tikzpicture}[default,node distance=16mm,->,s/.style={minimum size=5mm}] \node (q0a) [state,s] {}; \draw ($(q0a) + (-10mm,0mm)$) -- (q0a); \node (q0b) [state,s,right of=q0a] {}; \node (q1a) [state,s,below of=q0a,node distance=14mm] {}; \node (q1b) [state,s,right of=q1a] {}; \node (q1c) [state,s,right of=q1b] {}; \node (q2a) [fstate,s,below of=q1b,node distance=14mm] {}; \draw (q0a) to[bend left=15] node [label,above] {$a$} (q0b); \draw (q0b) to[bend left=15] node [label,below] {$a$} (q0a); \draw (q0a) to node [label,left] {$a$} (q1a); \draw (q0b) to node [label,left] {$a$} (q1b); \draw (q0b) to node [label,above right] {$a$} (q1c); \draw (q1a) to[bend left=10] node [label,above right] {$b$} (q2a); \draw (q1a) to[bend left=-10] node [label,below left] {$c$} (q2a); \draw (q1b) to node [label,right] {$b$} (q2a); \draw (q1c) to node [label,below right] {$c$} (q2a); \begin{scope}[xshift=60mm,node distance=14mm] \node (n0) [state,s] {}; \draw ($(n0) + (-10mm,0mm)$) -- (n0); \node (n1) [state,s,below of=n0] {}; \node (n2) [fstate,s,below of=n1] {}; \draw (n0) to node [label,left] {$a$} (n1); \draw (n1) to[bend left=-15] node [label,left] {$b$} (n2); \draw (n1) to[bend left=15] node [label,right] {$c$} (n2); \draw (n1) to[rloop] node [label,right] {$a$} (n1); \end{scope} \end{tikzpicture} \end{center} \end{example} \pause\bigskip \begin{block}{Theorem} Minimising of \alert{NFAs} is \alert{PSpace-complete}. \end{block} The definition of PSpace-complete follows later. \end{frame} \subsection{Lexical Analysis} \themex{Lexical Analysis}