\begin{frame}{Language Accepted by a Pushdown Automaton} A \emph{configuration} $(q,w,u)$ of an NPDA consists of: \smallskip \begin{itemize}\setlength{\itemsep}{0pt} \item current state \alert{$q \in Q$} \item input word \alert{$w \in \Sigma^*$} \item current stack \alert{$u \in \Gamma^*$} \end{itemize} \pause\medskip \begin{goal}{} The \emph{step relation} on configurations is defined by \begin{talign} (q,\, \alpha w,\, bu) \vdash (q',\, w,\, vu) \end{talign} whenever $(q',v) \in \delta(q,\alpha,b)$. \end{goal} We write $\vdash^*$ for computation (zero or more steps). \pause\medskip \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. \bigskip \end{frame}