Algorithm to decide the Kleene Star of a Language A

Assume $f$ decides a language $A$ in $O(g(n))$ time, where $n$ is the length of the input string. How to write a recursive algorithm to decide $A^*$ (recursive)?

Moreover, can an $O(n^2g(n))$ time algorithm be written to decide $A^*$ (dynamic programming)?

Yes, the dynamic programming portion is a hw assignment. CLRS book recommends using recursion first, then evolving to memoization, then the bottom-up approach. I can't even see how to write a recursive algorithm to solve this.

• What have you tried and where did you get stuck? Hint: try to answer the first question first, that is construct an algorithm with any runtime. In doing so, you will see which issue makes for a long runtime (if you are not smart from the start) and can try to address it using a smart recursion with memoization (i.e. dynamic programming). – Raphael Mar 6 '15 at 7:35
• My hint. $w\in A^*$ iff $w=\lambda$ (the empty string) or $w=w' v$, where $v\in A$ and $w'\in A^*$. – Hendrik Jan Mar 6 '15 at 11:56
• I got stuck trying to make a recursion function to do this. For instance, assume A = ['0','10'], x = '101010', then I can make a recursion function to solve that, but it fails on y = '010101'. Similarly if we just change A to equal ['0','01'] and run it on x. – intdt Mar 6 '15 at 21:56

First, solve the problem recursively:

def D(w)
if w = emptystring, return true.
for i = 1 to n
Let wp be the postfix of w of length i, let w2 be w with wp removed.
if f(wp) then
if D(w2) then
return true
endif
endif
endfor

return false
end


Now, if we just run $D(w)$ on all prefixes of $w$, remembering the result, then the time complexity is $O(n^2 g(n))$.

• Why would that be correct? What is the (algorithmic) idea and what is the core argument for why this works? – Raphael Mar 10 '15 at 7:37