k$-$depth PDA Section X only $(6$ points$)$ For any positive integer k$,$ let a k$-$depth PDA

be a PDA that can manipulate the characters at a specific index of the stack, rather

than just the top; in particular, it can manipulate only up to the k$$th character from

the top. Thus the transition function contains elements of the form $($p$,$ x$,$ a$,$ i$)($q$,$ b$),$

where i is a positive integer less than or equal to k$.$ The given transition signifies $$In

state p$,$ when reading an x from the input and the stack is at least i characters tall

with an a in the i$$th position from the top, switch to state q$,$ remove a from the stack

directly and put b in its place.$$ As before, x$,$ a$,$ and b may be $.$

Notice then that a $1-$Depth PDA is just a PDA. Prove that for any k$-$depth PDA P

there is a regular PDA P $$ such that L$($P $)=$ L$($P $).$

As a hint, first consider the case of showing there exists a PDA for every $2-$Depth

PDA