EN$-$US

$1$

$.$

$2$

$0$

$$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$

$.$

$2$

$0$

$$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

$1$

$3$

$$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.