PDA kleene star construction

Question

I know how to prove that CFL are closed under kleene star operation using CFG. I can't find online or in class notes a proof using PDA. I would appreciate description of the basic idea (not formal).

Answer 1

Use a PDA. Suppose you have a PDA for language $L$ and you want to recognize $L^*$. Given an input $x$, it is in $L^*$ if it can be partitioned as the concatenation $x=x_1 \cdots x_n$ of words $x_i$, where each $x_i \in L$. Construct a PDA as follows: the PDA nondeterministically guesses the end of each $x_i$ (the boundary between $x_i$ and $x_{i+1}$); if it guesses that it is at a boundary, it checks that it is in an accept state and then pops everything off the stack and then transitions to its start state and continues from there.