# How to know maximum final states in a DFA?

If a NFA contains N states, then Equivalent DFA can have atmost $2^N$ states.

Is there any method or any concept to know, how many final and non-final states will be there in the equivalent DFA ?

Take for example : An NFA has 7 states out of which 3 are final states. Its equivalent DFA can have atmost 128 states.

Then is there any method to find maximum number of final states and non final states in converted equivalent DFA ?

• What are your thoughts on the subject? Have you tried using the definition of the set of final states in the powerset construction? – Yuval Filmus Oct 31 '16 at 8:34
• @YuvalFilmus, yes I tried that. Like for this example, 4 non final states are there and powerset will include 16 states which form 16 non final states in DFA. So, i think 128 - 16 = 112 is the maximum number of final states, this DFA can have . what do u think ? – Garrick Oct 31 '16 at 10:21
• It seems like you have a conjecture. I encourage you to try and prove it - that's how we know if conjectures are true or not. – Yuval Filmus Oct 31 '16 at 10:24
• Are you interested in an upper bound for all NFA or in methods to determing the number of states given an NFA? – Raphael Oct 31 '16 at 19:16
• @Raphael, It would be good if i am given a NFA and after converting to equivalent DFA, i am able to tell maximum final states it could contain ?Like i have given an example in the question. – Garrick Nov 1 '16 at 2:41

$$F' = \{ S \mid S \cap F \neq \emptyset\}$$
If there are $n$ states in $Q$ and $k$ final stages in $F$, then there are $2^k-1$ nonempty subsets of $F$ and each of these can be occur together with a subset of the $n-k$ states that are not final.