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).
1
-
1$\begingroup$ It is very similar to the proof that regular languages are closed under Kleene star using $\epsilon$-NFAs. $\endgroup$– Yuval FilmusJul 28, 2020 at 16:35
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
