1
$\begingroup$

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

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

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.

$\endgroup$

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.