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