Timeline for Emptiness and determinization of NFAs
Current License: CC BY-SA 2.5
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 13, 2010 at 3:17 | answer | added | Joel David Hamkins | timeline score: 2 | |
| May 12, 2010 at 18:47 | answer | added | Niall Murphy | timeline score: 0 | |
| May 12, 2010 at 18:37 | answer | added | Grigory Yaroslavtsev | timeline score: 6 | |
| May 12, 2010 at 8:43 | comment | added | Neel Krishnaswami | @Aryeh: I edited your question to reflect your comment. | |
| May 12, 2010 at 8:42 | history | edited | Neel Krishnaswami | CC BY-SA 2.5 |
Fixed question
|
| May 12, 2010 at 8:06 | comment | added | Aryeh Kontorovich | Oops, my mistake!!! I didn't mean emptiness -- I meant L(NFA) = \Sigma^*. That is, rather than checking whether NFA accepts no strings (trivial) I want to know if it accepts ALL strings. | |
| May 12, 2010 at 7:48 | comment | added | Harry Altman | Can't emptiness just be determined by searching the graph? That's O(n^2) at most, right? | |
| May 12, 2010 at 7:30 | history | asked | Aryeh Kontorovich | CC BY-SA 2.5 |