\begin{frame}{($\Rightarrow$) From NFAs to Regular Expressions (3)}
  \begin{block}{}%[$\Rightarrow$ continued]
    \emph{Step 3:}
    \smallskip
    Pick \alert{one} state $q$ that is neither a starting nor a final state (if it exists).
    We remove $q$ as follows.
    \pause\medskip
    
    For all states $q_1$ and $q_2$ and arrows $q_1 \stackrel{r_1}{\to} q$ and $q \stackrel{r_2}{\to} q_2$,
    we add an arrow from $q_1$ to $q_2$ as follows:
    \begin{center}\vspace{-1.5ex}
    \begin{tikzpicture}[default,node distance=15mm,->,s/.style={minimum size=5mm}]
      \node (q1) [state,s] {$q_1$};
      \node (q) [state,s,right of=q1] {$q$}; 
      \node (q2) [state,s,right of=q] {$q_2$}; 
  
      \draw (q1) to node [above] {$r_1$} (q);
      \draw (q) to node [above] {$r_2$} (q2);
      \draw (q) to[tloop] node [above] {$r$} (q);
      
      \node at (40mm,0mm) {$\Rightarrow$};
      
      \begin{scope}[xshift=50mm]
      \node (q1) [state,s] {$q_1$};
      \node (q) [state,s,right of=q1] {$q$}; 
      \node (q2) [state,s,right of=q] {$q_2$}; 
  
      \draw (q1) to node [above] {$r_1$} (q);
      \draw (q) to node [above] {$r_2$} (q2);
      \draw (q) to[tloop] node [above] {$r$} (q);
      
      \draw [red] (q1) to[bend left=-20] node [below,rectangle] {$r_1\cdot r^* \cdot r_2$} (q2);
      \end{scope}
    \end{tikzpicture}\vspace{-2ex}
    \end{center}
    for the case that there is an arrow $q \stackrel{r}{\to} q$, and otherwise: 
    \begin{center}\vspace{-1.5ex}
    \begin{tikzpicture}[default,node distance=15mm,->,s/.style={minimum size=5mm}]
      \node (q1) [state,s] {$q_1$};
      \node (q) [state,s,right of=q1] {$q$}; 
      \node (q2) [state,s,right of=q] {$q_2$}; 
  
      \draw (q1) to node [above] {$r_1$} (q);
      \draw (q) to node [above] {$r_2$} (q2);
      
      \node at (40mm,0mm) {$\Rightarrow$};
      
      \begin{scope}[xshift=50mm]
      \node (q1) [state,s] {$q_1$};
      \node (q) [state,s,right of=q1] {$q$}; 
      \node (q2) [state,s,right of=q] {$q_2$}; 
  
      \draw (q1) to node [above] {$r_1$} (q);
      \draw (q) to node [above] {$r_2$} (q2);
      
      \draw [red] (q1) to[bend left=-20] node [below,rectangle] {$r_1\cdot r_2$} (q2);
      \end{scope}
    \end{tikzpicture}\vspace{-2ex}
    \end{center}
    \pause
    Note that $q_1$ can be equal to $q_2$. 
    \pause\medskip

    Afterwards adding all these transitions we remove $q$.
    \pause\medskip
    
    We \alert{repeat} Step 2 and Step 3 until there is nothing to be done.
  \end{block}
  \vspace{10cm}
\end{frame}