# 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^*$$?

• "$M = (Q,\Sigma,Γ,\delta,q_0,⊥,\emptyset)$". By $\emptyset$, do you mean $M$ has no accepting state? – Apass.Jack Jan 15 at 17:22
• Do you have a specific question? – Raphael Jan 16 at 12:03

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.