Constructing a pushdown automaton that accepts L* Would appreciate if you could take a look at what I did and help me finish it.


  Given a pushdown automaton that accepts a language $L$ by final state, construct a pushdown automaton that accepts $L^*$. Use a "double bottom" if need be.


My attempt:

Given  $M = (Q,\Sigma,Γ,\delta,q_0,⊥,∅)$, we'll add a double bottom by altering the function: $\delta' := \delta'(q_0',\epsilon, ⊥')={(q_0, ⊥⊥)}$, so M' is basically $M' = (Q\cup{q_0',q_f},\Sigma,Γ∪{⊥'},\delta',q_0',⊥',{q_f})$. The accepting state is reached by $\forall q \in Q\colon \delta' (q,\epsilon,⊥')={(q_f,⊥')}$.

How do I finish it so that it accepts $L^*$?
The Kleene star is, as you know, the union $\bigcup_n L^n$ of arbitrary powers $L\cdot L\cdot\ldots\cdot L$ of $L$.

If $M$ is the automaton that accepts $L$, then in order to make an automaton for $L^*$ you basically have to make it possible to restart the automaton after accepting $L$. Be careful in choosing final state or empty stack acceptance.