89/122
\begin{frame}{Paths in NFAs}
Let $M = (Q,\Sigma,\delta,S,F)$ be a NFA.
\begin{block}{}
For a word $w$, we write
\begin{talign}
\end{talign}
if $w = \alpha_1 \cdots \alpha_n$ for some $\alpha_1, \ldots, \alpha_n \in (\Sigma \alert{\cup \{\lambda\}})$
and there are states $q_1,\ldots,q_{n-1}$ such that
\begin{talign}
q_{n-1} \stackrel{\alpha_n}{\to} q'
\end{talign}
\end{block}
\pause
\begin{exampleblock}{}
\centerline{
\begin{tikzpicture}[default,node distance=15mm,->]
\node (q0) [state] {$q_0$}; \draw ($(q0) + (-10mm,0mm)$) -- (q0);
\node (q1) [fstate,right of=q0] {$q_1$};
\node (q2) [state,right of=q1] {$q_2$}; \draw ($(q2) + (10mm,0mm)$) -- (q2);
\draw (q0) to[bend left=10] node [label,above] {$a$} (q1);
\draw (q0) to[bend left=-10] node [label,below] {$\lambda$} (q1);
\draw (q1) to[bend left=0] node [label,above] {$b$} (q2);
\draw (q1) to[tloop] node [label,above] {$b$} (q1);
\draw (q2) to[out=-120,in=-60,looseness=0.5] node [label,below] {$a$} (q0);
\begin{scope}[nodes={rectangle}]
\node at (5.7cm,0.2cm) [align=left] {
$q_0 \apath{\lambda} q_0$\\[0mm]
$q_0 \apath{\lambda} q_1$\\[0mm]
$q_1 \apath{b} q_1$\\[0mm]
$q_1 \apath{b} q_2$
};
\end{scope}
\begin{scope}[nodes={rectangle}]
\node at (8.5cm,0.2cm) [align=left] {
$q_1 \apath{ba} q_0$\\[0mm]
$q_1 \apath{ba} q_1$\\[0mm]
$q_0 \apath{abbab} q_1$\\[0mm]
$q_0 \apath{abbab} q_2$
};
\end{scope}
}
\end{exampleblock}
\pause

\begin{goal}{}
Theorem: \;\;$q \apath{w} q' \;\iff\; (q,w) \vdash^* (q',\lambda)$.
\end{goal}
\end{frame}