\documentclass[10pt]{article}
\usepackage[letterpaper,margin=1in]{geometry}
\usepackage{amsmath,amsthm,amssymb,latexsym}
\usepackage{array,multirow,alltt,enumerate,bbm,eucal,graphicx}
\usepackage[colorlinks]{hyperref}
\usepackage{xcolor,stmaryrd,bussproofs,mathpartir}
\usepackage{tikz,pgfmath}
\usepgflibrary{shapes}
\usetikzlibrary{arrows,automata,backgrounds}

\setlength\parindent{0in}
\addtolength\parskip{1ex}
\setlength\fboxrule{.5mm}\setlength{\fboxsep}{1.2mm}
\newlength\courseheader
\courseheader=\textwidth
\addtolength\courseheader{-4mm}
\parindent=0pt
\parskip=1ex

%macro definitions

\newcommand\eps{\varepsilon}
\renewcommand\emptyset{\varnothing}
\newcommand\Imp{\Rightarrow}
\renewcommand\hat{\widehat}
\newcommand\set[2]{\{#1\mid#2\}}
\newcommand\Iff\Leftrightarrow
\newcommand\Iffdef{\stackrel{\mathrm{def}}\Leftrightarrow}

%environment definitions

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}

\begin{document}

\begin{center}
\framebox{\parbox\courseheader{\large Introduction to Theory of Computing\hfill Homework 7\\ 
CS 4810 Spring 2022\hfill Due Monday, 21 March 2022}}
\end{center}
\medskip

\pagestyle{empty}

\noindent
Our prelim is scheduled for \textbf{Thursday, March 24}, in class. The exam will be 75 minutes, open book and notes, no electronics. You will be responsible for all material covered in class up through and including the 3/17 lecture, except for the 2/17 and 2/22 lectures on automata and coalgebras. There will be a review session on Tuesday 3/22 in class in which we will go over the syllabus for the exam and answer questions.

Due to the prelim next week, this is a short assignment, which should take you no more than an hour or two. Also there is no quiz this week.

\hrulefill

Consider the set $E = \set{z\in\{a,b\}^*}{\#a(z)=\#b(z)+1}$, the set of all strings in $\{a,b\}^*$ with one more $a$ than $b$. The grammar
\begin{align*}
A \to aAB \mid aBA \mid bAA \mid a \qquad B \to bAB \mid bBA \mid aBB \mid b
\end{align*}
with start symbol $A$ is a Greibach normal form grammar generating $E$.


\begin{enumerate}
\item
Give a leftmost derivation of the string $baaabab$. A \emph{leftmost derivation} is one in which in each step, a production is applied to the leftmost remaining nonterminal in the sentential form.

\item
Here is a parse tree for $baaabab$.
\begin{center}
\begin{tikzpicture}[-, auto, node distance=7mm]
\small
\node (00) {$A$};
\node (11) [below of=00] {$A$};
\node (10) [left of=11] {$b$};
\node (12) [right of=11] {$A$};
\node (20) [below of=12] {$a$};
\node (21) [right of=20] {$A$};
\node (22) [right of=21] {$B$};
\node (2m) [left of=20] {$a$};
\node (30) [below of=21] {$a$};
\node (31) [below of=22] {$b$};
\node (32) [right of=31] {$A$};
\node (33) [right of=32] {$B$};
\node (40) [below of=32] {$a$};
\node (41) [below of=33] {$b$};
\path (00) edge (10) edge (11) edge (12);
\path (11) edge (2m);
\path (12) edge (20) edge (21) edge (22);
\path (21) edge (30);
\path (22) edge (31) edge (32) edge (33);
\path (32) edge (40);
\path (33) edge (41);
\end{tikzpicture}
\end{center}
In the proof of the Pumping Lemma for $z=baaabab$, all of the following partitions $u,v,w,x,y$ with $z=uvwxy$ would allow pumping; that is, for each of (a)-(e), $uv^iwx^iy\in E$ for all $i\ge 0$. However, only one of these partitions satisfies the specifications of the Pumping Lemma. Identify the good partition and say why the others are bad.
\begin{align*}
& \mathrm{(a)}\ \eps,b,a,aabab,\eps
&& \mathrm{(b)}\ \eps,ba,aabab,\eps,\eps
&& \mathrm{(c)}\ \eps,baa,a,bab,\eps
&& \mathrm{(d)}\ \eps,baaab,a,b,\eps
&& \mathrm{(e)}\ baaa,ba,b,\eps,\eps
\end{align*}

\item
Complete the following definition of a nondeterministic PDA for $E$ that accepts by empty stack.
\begin{align*}
M &= (\{*\},\{a,b\},\{A,B\},\delta,*,A,\emptyset)
\end{align*}
where $\delta$ consists of the following transitions:
\begin{enumerate}
\item \parbox{6cm}{$((*,a,A),(*,AB))$}(e)
\item \parbox{6cm}{$((*,a,A),(*,BA))$}(f)
\item \parbox{6cm}{$((*,b,A),(*,AA))$}(g)
\item \parbox{6cm}{\ }(h)
\end{enumerate}

\item
Give a sequence of configurations on input $baaabab$ starting from the 
start configuration $(*,baaabab,A)$ leading to acceptance by empty stack.
\end{enumerate}

\end{document}
