Timeline for Can we efficiently convert from NFA to smallest equivalent DFA?
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 23, 2021 at 8:31 | comment | added | Michael Wehar | @HermannGruber Thank you very much for your comment! This is a very neat insight. :) | |
| Mar 23, 2021 at 8:06 | comment | added | Hermann Gruber | @Michael Wehar nice question. Well, my gut feeling tells me that your followup approach shares the same doom. On the positive side, your idea works in the case where the NFA in your hands is the reverse minimum DFA for L^R. (Why? Brzozowski's algorithm.) | |
| Mar 23, 2021 at 7:55 | comment | added | Aryeh | Sure, great question. I’ll need to think about it... | |
| Mar 23, 2021 at 0:07 | comment | added | Michael Wehar | Maybe I will ask this as a separate question. What do you think? | |
| Mar 23, 2021 at 0:06 | comment | added | Michael Wehar | I guess my follow-up question is, what if $A$ is known to be a minimum NFA? Maybe the powerset construction does produce a minimum DFA in this case? I am not quite sure. | |
| Mar 23, 2021 at 0:03 | comment | added | Michael Wehar | Yes, you are totally right! I somehow didn't think of this. Thank you. :) | |
| Mar 23, 2021 at 0:02 | vote | accept | Michael Wehar | ||
| Mar 22, 2021 at 22:07 | history | answered | Aryeh | CC BY-SA 4.0 |