COMPUTER SCIENCE AND ENGINEERING
THEORY OF COMPUTATION
|
Question
[CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
|
|
|
exponential time
|
|
|
linear time
|
|
|
logarithmic time
|
|
|
all of the mentioned
|
Detailed explanation-1: -Explanation: We can eliminate e-transitions from an n state epsilon-NFA to build an ordinary NFA in O(n3) time, without changing the number of states. Next, producing to DFA can take exponential time. 7.
Detailed explanation-2: -As, far as I know, there is no unique solution for a conversion from DFA to NFA. Therefore, your answer is not challengeable. Although, you can try and make the tightest possible state diagram. Whereas, when you are converting an NFA to DFA, you will find a unique solution.
Detailed explanation-3: -Explanation: Yes it can be done through power set construction.
Detailed explanation-4: -Detailed Solution A state in a DFA will be a subset of the set of states of the equivalent NFA. So, the maximum number of states in the equivalent DFA of an NFA, will be 2n, where n is the number of states in NFA, as a set with n items has maximum 2n subsets.