\documentclass[letterpaper,12pt]{article}
\usepackage[dvips]{color}
\usepackage{epsfig}
\usepackage{gastex}
\setlength{\textwidth}{7.0in} \setlength{\evensidemargin}{-.3in}
\setlength{\oddsidemargin}{-.3in} \setlength{\topmargin}{-1.0in}
\textwidth 7.0in \textheight 4.7in \setlength{\footskip}{.8in}
\pagestyle{plain}
% M A C R O S
% EXAMPLE \noindent \textbf{\textcolor[rgb]{0.00,0.00,0.63}{Example}}:
% THEOREM \noindent \textbf{\textcolor[rgb]{0.00,0.00,0.63}{Thm.}}:
% PROOF \noindent \textbf{\textcolor[rgb]{0.00,0.00,0.63}{Proof}}:
% DEFINITION \noindent \textbf{\textcolor[rgb]{0.00,0.00,0.63}{Def.}}: A \textcolor[rgb]{0.90,0.00,0.0}{\textbf{generalized transition graph (GTG)}}
% SECTION \section*{\Large \sc \textcolor[rgb]{0.00,0.30,0.00}{3.12 Connection Between Regular Expressions \& Regular Languages}}
% SUBSECTION \subsection*{\large \sc \textcolor[rgb]{0.00,0.30,0.00}{3.12 Connection Between Regular Expressions \& Regular Languages}}
% SUBSUBSECTION \subsubsection*{\large \sc \textcolor[rgb]{0.00,0.30,0.00}{3.12 Connection Between Regular Expressions \& Regular Languages}}
%\begin{figure}[htbp]
%\centerline{\psfig{figure=figs/graph32l.eps,width=4.0in,clip=}}
%\caption{Speedup over $T_4$ for varying depth increments.}
%\label{fig:graph32l}
%\end{figure}
%\begin{center}
%\begin{picture}(80,60)
%\node(0)(20,30){-}
%\node(1)(40,40){+}
%\node(2)(60,40){+}
%\node(3)(40,20){}
%\node(4)(60,20){+}
%\drawedge(0,1){a}
%\drawedge[ELside=r](0,3){b}
%\drawedge(1,2){a}
%\drawedge[sxo=-1,syo=-1,curvedepth=4](1,3){b}
%\drawedge[sxo=-1,syo=-1,curvedepth=4](3,1){a}
%\drawloop[loopangle=0](2){a}
%\drawedge[sxo=-1,syo=-1,curvedepth=4](2,4){b}
%\drawedge[sxo=-1,syo=-1,curvedepth=4](4,2){a}
%\drawloop[loopangle=0](4){b}
%\drawedge(3,4){b}
%\end{picture}
%\end{center}
\begin{document}
\title{ \textcolor{red}{\Huge \sc Chapter 7: Pushdown Automata (PDA)}\footnote{Based on {\bf An Introduction to Formal Languages and Automata},
3rd Ed., Peter Linz, Jones and Bartlett Publishers, Inc. } }
\author{
Peter Cappello \\
Department of Computer Science \\
University of California, Santa Barbara \\
Santa Barbara, CA 93106 \\
cappello@cs.ucsb.edu
}
\date{}
\maketitle
\begin{itemize}
\item Please read the corresponding chapter before attending this lecture.
\item These notes are supplemented with figures, and material that arises during the lecture in
response to questions.
\item Please report any errors in these
notes to \verb"cappello@cs.ucsb.edu". I'll fix them immediately.
\end{itemize}
{\Large
\section*{\Large \sc \textcolor[rgb]{0.00,0.30,0.00}{7.1 Nondeterministic Pushdown Automata}}
\subsection*{\large \sc \textcolor[rgb]{0.00,0.30,0.00}{Definition of a Pushdown Automaton \textcolor[rgb]{1.00,0.00,0.00}{(Illustrate schematic of PDA.)}}}
\noindent \textbf{\textcolor[rgb]{0.00,0.00,0.63}{Def. 7.1}}: A
\textcolor[rgb]{0.90,0.00,0.0}{\textbf{nondeterministic pushdown
acceptor (NPDA)}} is a 7-tuple
%\[
$M = (Q, \Sigma, \Gamma, \delta, q_0 , z, F)$, where
%\]
\begin{description}
\item[$Q$] is a finite set of states of the control unit,
\item[$\Sigma$] is a finite input alphabet,
\item[$\Gamma$] is a finite \textbf{stack alphabet},
\item[$\delta$:] $Q \times (\Sigma \cup \{ \lambda \} ) \times
\Gamma \mapsto$ \emph{finite} subsets of $Q \times \Gamma^*$ is the
transition function,
\item[$q_0$] is the initial state,
\item[$z \in \Gamma$] is the \textbf{stack start symbol},
\item[$F \subseteq Q$] is the set of final states.
\end{description}
\newpage
\begin{itemize}
\item
The range of $\delta$ is a set of ordered pairs.
\item
The 1st component of these ordered pairs is the successor
state.
\item
The second component is a sequence of stack symbols that
replace the top stack symbol.
For example, if the current stack symbol is $\alpha$ and the
ordered pair specified $(q, \alpha \beta \gamma)$, then, in effect,
we execute the following sequence:
pop \newline push($\gamma$) \newline
push($\beta$) \newline push($\alpha$).
\item
The set $Q \times \Gamma^*$ is infinite, and hence has infinite subsets.
We disallow the set of successor pairs to be infinite.
\end{itemize}
\newpage
\noindent \textbf{\textcolor[rgb]{0.00,0.00,0.63}{Example}}: Let
$M = ( \{ q_0 , q_1 , q_2 \}, \{ a, b \}, \{ 0, 1 \}, \delta, q_0,
0, \{ q_3 \} )$ be a NPDA with $\delta$ indicated diagrammatically
below.
\textcolor[rgb]{1.00,0.00,0.00}{(Draw $M$'s control.)}
\begin{itemize}
\item
Does $M$ accept $\lambda$?
\item
Does $M$ accept $a$?
\item
Does $M$ accept $ab$?
\end{itemize}
\newpage
\begin{itemize}
\item
An \textbf{instantaneous description (ID)} gives all the relevant
information about the current state of an NPDA:
\begin{itemize}
\item
The current state;
\item
The unread portion of the input;
\item
The current contents of the stack.
\end{itemize}
\item
The operation of an NPDA can be depicted as a sequence of IDs,
starting from the initial ID: $(q_0, w, z_0)$, where the input
is $w$ and $z_0$ is the start stack symbol.
\item
A move from ID $(q_i, aw, bx)$ to ID $(q_j, w, yx)$ is
denoted
\[
(q_i, aw, bx) \vdash (q_j, w, yx) ,
\]
and is possible if and only if
%\[
$( q_j , y ) \in \delta( q_i , a , b )$.
% \]
\item
The notation $ID_i \vdash^* ID_j$ denotes a sequence of moves from $ID_i$ to
$ID_j$.
\end{itemize}
\newpage
\subsection*{\large \sc \textcolor[rgb]{0.00,0.30,0.00}{The Language Accepted by a PDA}}
\noindent \textbf{\textcolor[rgb]{0.00,0.00,0.63}{Def. 7.2}}: Let
$M = (Q, \Sigma, \Gamma, \delta, q_0, z, F)$ be a NPDA.
\newline
The language accepted by $M$ is
\[
L(M) = \{ w \in \Sigma^* : (q_0, w, z) \vdash_M^* (p, \lambda, u),
p \in F, u \in \Gamma^* \}.
\]
The final stack content, $u$, is irrelevant.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
}
\end{document}