106/110
\begin{frame}{($\Rightarrow$) From NFA's to Regular Expressions (4)}
\begin{construction}[$\Rightarrow$ continued]
\emph{Step 4:}
\smallskip

If $F \neq \{q_0\}$, then the transition graph is finally of the form:
\begin{center}\vspace{-1ex}
\begin{tikzpicture}[default,node distance=20mm,->,s/.style={minimum size=5mm}]
\node (q0) [state] {$q_0$}; \draw ($(q0) + (-8mm,0mm)$) -- (q0);
\node (qf) [fstate,right of=q0] {};

\draw (q0) to[bend left=20] node [above] {$r_2$} (qf);
\draw (qf) to[bend left=20] node [below] {$r_3$} (q0);
\draw (q0) to[tloop] node [above] {$r_1$} (q0);
\draw (qf) to[tloop] node [above] {$r_4$} (qf);
\end{tikzpicture}\vspace{-1.5ex}
\end{center}
\pause
Possibly $r_1$, $r_2$, $r_3$ or $r_4$ are equal to $\emptyset$.
\pause\medskip

Then the regular expression is:
\pause
\begin{talign}
\alert{L(r_1^*\cdot r_2\cdot (r_4 + r_3\cdot r_1^*\cdot r_2)^*)~=~L(M)}
\end{talign}
\end{construction}
\pause

\begin{question}
What is the form of the transition graph and regular expression for the case that $F=\{q_0\}$\,?
\end{question}
\vspace{10cm}
\end{frame}