1 votes 1 votes running time of NFA to DFA conversion including the case where NFA has $\epsilon$-transition is ? Theory of Computation theory-of-computation time-complexity + – monali asked Nov 24, 2015 monali 3.3k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 5 votes 5 votes For a given NFA of n state, the number of states in equivalent DFA is at most 2n. So worst case complexity is O(2n). Digvijay Pandey answered Nov 25, 2015 • edited Jan 10 by Hira Thakur Digvijay Pandey comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments Tendua commented Nov 25, 2015 reply Follow Share what will be the algorithm to do this . and what will be the complexity for converting regular expression to nfa. 0 votes 0 votes Pragy Agarwal commented Nov 25, 2015 reply Follow Share @Ravi: There is a standard, easy to follow and pretty straight forward algorithm for it. See: Converting a regular expression to a NFA - Thompson's Algorithm. You might also wanna read this algorithm from a standard book. This online tool will help you see it in action: http://hackingoff.com/compilers/regular-expression-to-nfa-dfa 2 votes 2 votes Tendua commented Nov 26, 2015 reply Follow Share thanks i was always confused. 1 votes 1 votes Please log in or register to add a comment.
