\begin{frame}{Paths in DFAs} Let $M = (Q,\Sigma,\delta,q_0,F)$ be a DFA. \begin{block}{} For a word $w = a_1 \cdots a_n$, $n \ge 0$, we write \begin{talign} \alert{q_0 \apath{w} q_n} \end{talign} if there are states $q_1,\ldots,q_{n-1}$ such that \begin{talign} q_0 \stackrel{a_1}{\to} q_1 \quad\quad q_1 \stackrel{a_2}{\to} q_2 \quad\quad \ldots \quad\quad q_{n-1} \stackrel{a_n}{\to} q_n \end{talign} \end{block} \pause \begin{exampleblock}{} \centerline{ \begin{tikzpicture}[default,node distance=20mm,->] \node (q0) [fstate] {$z_0$}; \draw ($(q0) + (-10mm,0mm)$) -- (q0); \node (q2) [state,right of=q0,yshift=-10mm] {$z_2$}; \node (q1) [fstate,right of=q2,yshift=10mm] {$z_1$}; \draw (q0) to[bend left=15] node [label,above left] {$a$} (q1); \begin{scope}[label/.style={inner sep=0.5mm}] \draw (q0) to[bend left=10] node [label,above right] {$b$} (q2); \draw (q1) to[bend left=10] node [label,below right,inner sep=0mm] {\alert<1>{$a,b$}} (q2); \draw (q2) to[bend left=10] node [label,above left] {$a$} (q1); \draw (q2) to[bend left=10] node [label,below left] {$b$} (q0); \end{scope} \begin{scope}[nodes={rectangle}] \node at (6.5cm,-0.3cm) [align=left] { $z_1 \apath{\lambda} z_1$\\[1mm] $z_0 \apath{ab} z_2$\\[1mm] $z_0 \apath{abba} z_1$ }; \end{scope} \end{tikzpicture}\quad } \end{exampleblock} \pause\bigskip \begin{goal}{} Theorem: \;\;$q \apath{w} q' \;\iff\; (q,w) \vdash^* (q',\lambda)$. \end{goal} \end{frame}