0
$\begingroup$

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

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

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ thank you! I got it $\endgroup$ – Ella Jul 29 at 5:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.