Question $7$

$[14]$

Consider the partially complete $2$PDA given below. This $2$PDA, when complete, should recognise the language $L$ as defined below:

$L=\{(a{)}^{n+1}bb(a{)}^{n}bb(a{)}^n|n0\}($Assume that the alphabet is $=\{a,b\}.)$

a$.$ What is the purpose of the section of the $2$PDA illustrated in box $A?$ Explain in detail how this purpose is achieved.

$(5)$

$5$

Cos$3701/$Oct$-$Nov $2022$

b$.$ What is the purpose of the section of the $2$PDA illustrated in box $B?$ Explain clearly what is being done here and how it affects or is affected by the overall design of the $2$PDA.

c$.$ Complete the $2$PDA by showing what should be included in Box $C$ of the diagram shown above.

Note that the edges shown in the diagram are the only edges that are needed between what is outside of Box C and what is needed inside Box C$.$

$(6)$