A PDA accepts by empty stack if the stack is empty when the input word has been completely

processed $($i$.$e$.,$ we do not distinguish between accepting and non$-$accepting states$).$ Consider the

following PDA. It has three states, the initial state s and states f and g$.$ It has the following

transitions, where $ is a bottom marker on the stack before the computation begins.

$(1)(($s$,$ a$,\backslash$epsi $)->($s$,$ a$))$

$(2)(($s$,$ b$,\backslash$epsi $)->($s$,$ b$))$

$(3)(($s$,\backslash$epsi $,\backslash$epsi $)->($f$,\backslash$epsi $))$

$(4)(($f$,$ a$,$ a$)->($f$,\backslash$epsi $))$

$(5)(($f$,$ b$,$ b$)->($f$,\backslash$epsi $))$

$(6)(($f$,\backslash$epsi $,$ $$)->($g$,\backslash$epsi $))$

a$)$ Trace the PDA on the following words w $($i$.$e$.,$ give the sequence of configurations

of a computation on input w$)$ and determine whether they are accepted by empty

stack.

$1.$ w $=$ abba

$2.$ w $=$ abb

b$)$ Describe the language accepted by the PDA.