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

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

1 Answer 1


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.


Your Answer

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

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