# PDA kleene star construction

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

• It is very similar to the proof that regular languages are closed under Kleene star using $\epsilon$-NFAs. – Yuval Filmus Jul 28 '20 at 16:35

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.