$1.20$ points Consider the following CFG G$.$

S $->$ XX $|$ Y

X $->$ aXb $|$ c

Y $->$ bbY c $|$ a

$($a$)$ Create MG$,$ an augmented PDA from G$.$

$($b$)$ Consider the augmented transition in the PDA created to mimic

the X $->$ aXb rule in the grammar. Show the non$-$augmented

sequence of transitions required in a standard PDA that would

mimic this rule.

$($c$)$ Let w $=$ aacbbacb. Provide a leftmost derivation of w in the

grammar G$,$ and show the computation path of w in MG$.$

S $->$

$->$

$[$q$0,$ aacbbacb, $\backslash$epsi $][$q$1,,]$

$[$qloop$,,]$

$2.20$ points Consider the following PDA P$.$

$($a$)$ Create a CFG that accepts L$($P$)$ using the method presented in

the videos. Make sure you label you variables to correspond with

the states in P as discussed in the videos and the text.

$($b$)$ Let w $=$ aabbbc. Show the computation path of w in P and provide

a leftmost derivation of w in G$.$

fig $1$

:$+$ pda

title WS$13$ Prob $2$

Q$=\{$qs$,$q$1,$q$2,$q$3,$qf$\}$

S$=\{$a$,$b$,$c$\}$

T$=\{$X$,$Y$,$$$\}$

q$0=$qs

F$=\{$qf$\}$

qs$->$q$1$:$\backslash$e$,\backslash$e$->$$

q$1$:a$,\backslash$e$->$X

q$1->$q$2$:a$,\backslash$e$->$X

q$2$:b$,$X$->\backslash$e

q$2$:b$,\backslash$e$->$Y

q$2->$q$3$:b$,\backslash$e$->$Y

q$3$:c$,$Y$->\backslash$e

q$3->$qf:$\backslash$e$,$$$->\backslash$e

done.