Let L be the language over $=\{$a$,$ b$\}$ of all strings that

contain at least one b in the second half of the string:

L $=\{$uv : u in $,$ v in $$b$$ and $|$u$||$v$|\}.$

Construct a PDA that recognizes L$.$

Exercise $2(25$ points$).$ Construct a grammar for the language in Exercise $1.$

Hint: see if you can create a set of production rules for a variable X that, during

a derivation, produces a new variable A only to the left, or equally to the left and

right: X $=$ AX $=$ AAX $=$ AAAXA $=.$