\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} \alert{q \apath{w} q'} \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 \stackrel{\alpha_1}{\to} q_1 \quad\quad q_1 \stackrel{\alpha_2}{\to} q_2 \quad\quad q_2 \stackrel{\alpha_3}{\to} q_3 \quad\quad \ldots \quad\quad 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{tikzpicture}\quad } \end{exampleblock} \pause \begin{goal}{} Theorem: \;\;$q \apath{w} q' \;\iff\; (q,w) \vdash^* (q',\lambda)$. \end{goal} \end{frame}