Problem $3[15$ points$]$

Consider the PDA $M=(Q=\{q,p,r,t\},=\{0,1\},=\{$$$,x\},,q_0=t,F=\{r\})$ with start

state $t,$ accepting state set $\{r\},$ and the following transition function:

$(t,,)=\{(q,$$$)\}$

$(q,0,)=\{(q,x)\}$

$(q,1,)=\{(q,),(p,)\}$

$(p,1,x)=\{(p,)\}$

$(p,,$$$)=\{(r,)\}$

All other triples are mapped by $$ to $\frac{O}{?}.$

a$.[7$ points$]$ Give all the computations of the PDA on input $0110.$

Show each computation in the form $(q_0,s_0)-w_1(q_1,s_1)-w_2(q_2,s_2)-w_3$dots,

where $q_i$inQ is the state in step $i,s_{i}in{}^{**}$ is the stack in step $i($thus $s_0=),$ and $w_i$ is the

input symbol read at step $i($if any$)$ or $.$ Include both the computations that read the

whole input as well as those that die $($get stuck$)$ before reading the whole input.

Is $0110$ in the language $L(M)$ of $M?$

Is $011$ in $L(M)?$

b$.[8$ points$]$ Describe in English the language $L(M).$ Justify your answer.Ask chegg professional