\begin{frame}{($\Rightarrow$) From NFAs to Regular Expressions (4)} \begin{block}{}%[$\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 If an arrow $r_i$ with $1 \le i \le 4$ does not exist, let $r_i = \emptyset$. %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{block} \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}