LEXICAL ANALYSIS
REGULAR EXPRESSIONS AND FINITE AUTOMATA
|
Question
[CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
|
|
|
O(m2)
|
|
|
O(2m)
|
|
|
O(m)
|
|
|
O(log m)
|
Detailed explanation-1: -The construction time for a DFA from an NFA is O(2^m) where m is the number of nodes. The running time of a DFA is O(n) where n is the length of the input string. This is because there is only 1 path through the DFA for a given string.
Detailed explanation-2: -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.
Detailed explanation-3: -DFA has only one move on a given input symbol. Let, M = (Q, ∑, , q0, F) is an NFA which accepts the language L(M). There should be equivalent DFA denoted by M’ = (Q’, ∑’, q0’, ’, F’) such that L(M) = L(M’).
Detailed explanation-4: -If NFA of 6 states excluding the initial state is converted into DFA, maximum possible number of states for the DFA is ? Explanation: The maximum number of sets for DFA converted from NFA would be not greater than 2n.