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.

  • 2
    $\begingroup$ 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). $\endgroup$ – Raphael Mar 6 '15 at 7:35
  • 1
    $\begingroup$ My hint. $w\in A^*$ iff $w=\lambda$ (the empty string) or $w=w' v$, where $v\in A$ and $w'\in A^*$. $\endgroup$ – Hendrik Jan Mar 6 '15 at 11:56
  • $\begingroup$ 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. $\endgroup$ – 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

  return false

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))$.

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

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.