1.

For a _________ state DFA, the time taken for DFA-NFA conversion is O(n).(a) n(b) n^1/2(c) n^2(d) 2^nI got this question by my school teacher while I was bunking the class.Question is from Conversions among Representations in division Properties of Regular Languages of Automata Theory

Answer»

The correct answer is (a) n

For EXPLANATION I would SAY: The conversion DFA to NFA is simple, and takes O(n) TIME on an n-state DFA.



Discussion

No Comment Found

Related InterviewSolutions