0 votes 0 votes Answer the following:- 1. Worst case time complexity to minimize DFA? 2. Best case time complexity to minimize DFA? 3. Worst case time complexity to minimize NFA? 4. Best case time complexity to minimize NFA? Theory of Computation theory-of-computation + – Naveen Kumar 3 asked Nov 8, 2018 Naveen Kumar 3 690 views answer comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments Vikas Verma commented Nov 8, 2018 reply Follow Share It should be $n^{2}$ 0 votes 0 votes Naveen Kumar 3 commented Nov 8, 2018 reply Follow Share But, a/c to Hopcroft's Algorithm, it is O(ns log n), where n is the number of states and s is the size of the alphabet 0 votes 0 votes Swapnil Naik commented Nov 8, 2018 reply Follow Share https://gateoverflow.in/209545/time-complexity-to-minimize-finite-automata https://gateoverflow.in/?qa=blob&qa_blobid=7498393159640278086 https://en.wikipedia.org/wiki/Powerset_construction 0 votes 0 votes Please log in or register to add a comment.
