LEXICAL ANALYSIS
REGULAR EXPRESSIONS AND FINITE AUTOMATA
Question
[CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]


8


32


64


128

Detailed explanation1: We have four state which is not finale so all these state which come together to form a state in dfa are not have any finale state in dfa. so possible dfa state with only these 4 states is 24 = 16 and total number of state is 27 = 128 so total number of state which contain final state is 12816 =112.
Detailed explanation2: 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 explanation3: The maximum number of states is 2n. Conversion from NFA to DFA is done by subset construction and the number of states of the resulting DFA is in the worst case 2n.
Detailed explanation4: Take for example : An NFA has 7 states out of which 3 are final states. Its equivalent DFA can have atmost 128 states.
Detailed explanation5: (Same as for DFA) Number of possible start states =n (assuming NFA can have only one start state) (Same as for DFA) Number of final states =2n, since any subset of states can be set of final states.