36/162
\begin{frame}{Exercises (2)}
\begin{exampleblock}{}
Draw an NPDA $M$ with \alert{$L(M) = \{\, ww^R \mid w \in \{a,b \}^+ \,\}$}.
\medskip

\structure{Hint}: define
\begin{talign}
Q &= \{\, q_0, q_1, q_2 \,\} & \Gamma &= \{\, a,b,z \,\} \\
\Sigma &= \{\, a,b \,\} & F &= \{\, q_2 \,\}
\end{talign}
\pause
We construct the NDPA as follows:
\begin{center}
\begin{tikzpicture}[default,node distance=30mm,->,s/.style={minimum size=5mm}]
\node (q0) [state,s] {$q_0$}; \draw ($(q0) + (-8mm,0mm)$) -- (q0);
\mpause[1]{\draw (q0) to[tloop] node [label,above,align=center] {$a[z/az]$\\$a[a/aa]$\\$a[b/ab]$} (q0);}
\mpause{\draw (q0) to[bloop] node [label,below,align=center] {$b[z/bz]$\\$b[a/ba]$\\$b[b/bb]$} (q0);}

\node (q1) [state,s,right of=q0] {$q_1$};
\mpause{\draw (q0) to node [label,above,align=center] {$a[a/\lambda]$\\$b[b/\lambda]$} (q1);}
\mpause{\draw (q1) to[tloop] node [label,above,align=center] {$a[a/\lambda]$\\$b[b/\lambda]$} (q1);}

\node (q2) [fstate,s,right of=q1] {$q_2$};
\mpause{\draw (q1) to node [label,above] {$\lambda[z/\lambda]$} (q2);}
\end{tikzpicture}
\end{center}
\end{exampleblock}
\end{frame}