Suppose M = (Q, ?, ?, ?, q0, F) is a PDA. We can define a new PDA N so that L(M) = L(N) and N is guaranteed to have an empty stack at the end of any accepting computation. Informally, the construction is as follows

a. Suppose M-Q.?, ?, ?, q ,F) is a PDA. We can define a new PDA N so that L(M)-L(N) and N is guaranteed to have an empty stack at the end of any accepting computation. Informally, the construction is as follows: Add three new states q,g,G and one new stack symbol # One of the new states will be the new start state and it has a spontaneous transition to the old start state go which pushes the new stack symbol # to the stack. - The transitions between the old states are all the same. From each of the old accept states, add a spontaneous transition (that doesn't modify the stack) to the second new state q2 - In this state q2, pop all old stack symbols from the stack without reading any input -When the new stack symbol # is on the top of the stack, transition to the third new state e and accept Complete the formalization of this description by filling in the blanks in the transition function below where we assume {q,,%-4, } n Q-0 and # ?, and ?f q ? Q.ze , y ? ?? 8'( (g,e,z) )= otherwise Some hints: The transition function of the PDA N has domain and codomain Make sure the outputs you specify when you fill in the blank are sets of ordered pairs of the right type. - The new machine N has only one accept state: the new state q% (where do you see this in the formal definition?) b. Suppose G-V, ?' R, S) and define the new grammar G' (V, ?' RUIS SS), S) i True or False: L(G) L(G) L(G) for all grammars G ii True or False: L(G)-(L(G))" for all grammars G iii True or False: L(G) DOUBLE(L(G)) for all grammars G a. Suppose M-Q.?, ?, ?, q ,F) is a PDA. We can define a new PDA N so that L(M)-L(N) and N is guaranteed to have an empty stack at the end of any accepting computation. Informally, the construction is as follows: Add three new states q,g,G and one new stack symbol # One of the new states will be the new start state and it has a spontaneous transition to the old start state go which pushes the new stack symbol # to the stack. - The transitions between the old states are all the same. From each of the old accept states, add a spontaneous transition (that doesn't modify the stack) to the second new state q2 - In this state q2, pop all old stack symbols from the stack without reading any input -When the new stack symbol # is on the top of the stack, transition to the third new state e and accept Complete the formalization of this description by filling in the blanks in the transition function below where we assume {q,,%-4, } n Q-0 and # ?, and ?f q ? Q.ze , y ? ?? 8'( (g,e,z) )= otherwise Some hints: The transition function of the PDA N has domain and codomain Make sure the outputs you specify when you fill in the blank are sets of ordered pairs of the right type. - The new machine N has only one accept state: the new state q% (where do you see this in the formal definition?) b. Suppose G-V, ?' R, S) and define the new grammar G' (V, ?' RUIS SS), S) i True or False: L(G) L(G) L(G) for all grammars G ii True or False: L(G)-(L(G))" for all grammars G iii True or False: L(G) DOUBLE(L(G)) for all grammars G