18/93
\begin{frame}{Language Accepted by a Pushdown Automaton}
When a NPDA reads a words, we need to keep track of:
\smallskip
\begin{itemize}\setlength{\itemsep}{0pt}
\item the current state \alert{$q \in Q$}
\item the remaining input \alert{$w \in \Sigma^*$}
\item the current stack \alert{$u \in \Gamma^*$}
\end{itemize}
\pause\smallskip

\begin{goal}{}
If $(q',v) \in \delta(q,\alpha,b)$, this means that
\begin{itemize}
\item from state \alert{$q$} with input \alert{$\alpha w$} and stack $\alert{b}u$
\end{itemize}
the automaton can do a transition to
\begin{itemize}
\item state \alert{$q'$} with input \alert{$w$} and stack $\alert{v}u$.
\end{itemize}
\pause
This is denoted by
\quad $\alert{(q,\, \alpha w,\, bu) \vdash (q',\, w,\, vu)}$.
\end{goal}
\pause

\begin{block}{}
The \emph{language generated by} NPDA
$M=(Q,\Sigma,\Gamma,\delta,q_0,z,F)$ is
\begin{talign}
L(M) = \{\, w \in \Sigma^* \mid (q_0,w,z) \vdash^* (q',\lambda,u) \text{ where } q' \in F \,\}.
\end{talign}
\end{block}
Note: no condition on the stack $u$ at the end. It is often empty.
\bigskip
\end{frame}