COMPILER DESIGN

Detailed explanation-1: -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 128-16 =112.

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: -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 explanation-4: -Take for example : An NFA has 7 states out of which 3 are final states. Its equivalent DFA can have atmost 128 states.

Detailed explanation-5: -(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.