Timeline for Equivalance of NFAs, understanding the solution
Current License: CC BY-SA 3.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 17, 2017 at 18:32 | comment | added | David Richerby | @Logic You're welcome. Glad I finally managed to explain it properly. :-) | |
| Aug 17, 2017 at 18:26 | vote | accept | Logic | ||
| Aug 17, 2017 at 16:59 | comment | added | David Richerby | @Logic You can't use that much memory but you don't need to. As I keep saying, you don't have to write the whole graph down. I've edited the answer to try to explain. | |
| Aug 17, 2017 at 16:59 | history | edited | David Richerby | CC BY-SA 3.0 |
Added a worked example.
|
| Aug 17, 2017 at 16:30 | comment | added | Logic | everything you said is true but it omits my question. My question is: Why does author of the solution to compute a space-complexity claims that size of automata is $2^{2n}$ whileas he cannot use so many memory? | |
| Aug 17, 2017 at 16:23 | comment | added | David Richerby | @Logic Man, if I could write something without making a bunch of typos, this would be a whole lot easier. What I meant to say is that you can do reachability on a graph with $2^n$ vertices in space $O(\log 2^n)$. You can do it on a graph of that size because you don't have to write the whole graph down. To do it on the fly, you just need to remember your current state (some subset of the NFA's states) and figure out what set of states you can move to by a transition. Just use the subset construction, but only construct things when you need them and forget them again once they've been used. | |
| Aug 17, 2017 at 16:14 | comment | added | Logic | "can be generated easily on the fly from the description of the NFA". I guessed you meant NFA. But, at least for me it is not easy to define how to generate such information on the fly. | |
| Aug 17, 2017 at 16:12 | comment | added | Logic | " Re your second, it's saying that you can do reachability on a graph with 2n vertices in space O(logn). It doesn't say that you have to write down the graph explicitly to do that.". Yes. But, again: See that authors compute memory taken by their algorithm: They say: "Thus, the problem can be decided in $NSPACE(log(2^{2n}))$". So they run algorithm to decide reachability on graph of size $2^{2n}$, do you agree? Why are they able to do it (to have a graph of that size). | |
| Aug 17, 2017 at 15:44 | comment | added | David Richerby | @Logic Re your first comment, I brainfarted and have fixed it. I meant to say that the state set and transitions of the DFA can be generated easily on the fly from the description of the NFA. Re your second, it's saying that you can do reachability on a graph with $2^n$ vertices in space $O(\log n)$. It doesn't say that you have to write down the graph explicitly to do that. Remember that the accounting for the space used to solve a problem is only the working space: it doesn't include the space required to write the input or the output. And, in this case, we don't even write the input. | |
| Aug 17, 2017 at 15:41 | history | edited | David Richerby | CC BY-SA 3.0 |
Typo -- confused NFA and DFA
|
| Aug 17, 2017 at 15:15 | comment | added | Logic | note that authors in the solution say: "Thus, the problem can be decided in $NSPACE(log(2^{2n}))$ so it means that they claim that REACHABILITY algorithm operates on precomputed (not computed on the fly) automaton. | |
| Aug 17, 2017 at 15:09 | comment | added | Logic | the solution from my post doesn't say how to get list of states. You said: "Both of these can be done easily, on the fly, from the description of the DFAs. ". I agree. But, we have no description of DFAs. For examaple, I am not sure that it is possible to generate a such information on the fly. | |
| Aug 17, 2017 at 13:15 | history | edited | David Richerby | CC BY-SA 3.0 |
Added another example.
|
| Aug 17, 2017 at 12:44 | history | answered | David Richerby | CC BY-SA 3.0 |