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
  • 1
    $\begingroup$ It is very similar to the proof that regular languages are closed under Kleene star using $\epsilon$-NFAs. $\endgroup$ Jul 28, 2020 at 16:35

1 Answer 1

2
$\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.

$\endgroup$
1
  • $\begingroup$ thank you! I got it $\endgroup$
    – Ella
    Jul 29, 2020 at 5:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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