29/122
\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}
\end{talign}
if there are states $q_1,\ldots,q_{n-1}$ such that
\begin{talign}
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}
Theorem: \;\;$q \apath{w} q' \;\iff\; (q,w) \vdash^* (q',\lambda)$.