\begin{frame}{($\Rightarrow$) From NFAs to Regular Expressions (2)} \begin{block}{}%[$\Rightarrow$ continued] \emph{Step 2:} \smallskip We remove all double arrows. \pause\medskip We use transition graphs with \alert{regular expressions as labels}. \pause\medskip If there are $2$ arrows from a state $q_1$ to $q_2$ with labels $r_1$ and $r_2$ replace them by one arrow with label $r_1 + r_2$: \begin{center} \begin{tikzpicture}[default,node distance=20mm,->,s/.style={minimum size=5mm}] \node (q1) [state,s] {$q_1$}; \node (q2) [state,s,right of=q1] {$q_2$}; \draw (q1) to[bend left=15] node [above] {$r_1$} (q2); \draw (q1) to[bend left=-15] node [below] {$r_2$} (q2); \node at (30mm,0mm) {$\Rightarrow$}; \begin{scope}[xshift=40mm] \node (q1) [state,s] {$q_1$}; \node (q2) [state,s,right of=q1] {$q_2$}; \draw (q1) to node [rectangle,above,inner sep=1mm] {$r_1 + r_2$} (q2); \end{scope} \end{tikzpicture} \end{center} \pause Note that $q_1$ can be equal to $q_2$. Then the arrows are loops! \pause\medskip \emph{We remove all double arrows before continuing with Step 3.} \end{block} \vspace{10cm} \end{frame}