1
$\begingroup$

Given an NFA, to decide if it accepts a word w, one could use the following algorithm: Transform the NFA into a DFA. Then, run w on the DFA and accept/reject if the DFA accepts/rejects.

Could this be done on a linear bounded automata? How do I know for sure that the encoding of the DFA won't go over the input space?

$\endgroup$
4
  • 1
    $\begingroup$ Welcome to CS.SE! When you say "Could this be done", can you edit your question to clarify what you mean by "this"? Do you mean, convert a linear bounded automaton to a DFA? Do you mean, run the DFA on w, but do it on a linear bounded automaton? If the latter, what did you have in mind as the inputs? Are you talking about the input including both the DFA and the word w; or just the word w (so the LBA depends on the DFA)? Also, what are your thoughts? $\endgroup$
    – D.W.
    Mar 14, 2017 at 21:00
  • $\begingroup$ I'm trying to figure out how to decide if an NFA accepts w on a linear bounded automata, but I think my algorithms use more than the input tape in terms of space. $\endgroup$
    – user67773
    Mar 14, 2017 at 21:03
  • 2
    $\begingroup$ Hint: perform the power-set construction implicitly, in-place, and for the given input only. $\endgroup$
    – Raphael
    Mar 14, 2017 at 21:05
  • $\begingroup$ I suggest that you edit the question so it is clearer, and to address all of the points in my comment. We want questions to be self-contained, so people don't have to read the comments to understand what you are asking. (Also, I still can't tell what the answer to some of my questions are, especially what's on the input tape for the LBA, so if you could edit the question to address all of those, that would be helpful.) $\endgroup$
    – D.W.
    Mar 14, 2017 at 21:05

0

Your Answer

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

Browse other questions tagged or ask your own question.