0
$\begingroup$

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 ?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ What are your thoughts on the subject? Have you tried using the definition of the set of final states in the powerset construction? $\endgroup$
    – Yuval Filmus
    Oct 31, 2016 at 8:34
  • $\begingroup$ @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 ? $\endgroup$
    – Garrick
    Oct 31, 2016 at 10:21
  • 1
    $\begingroup$ 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. $\endgroup$
    – Yuval Filmus
    Oct 31, 2016 at 10:24
  • $\begingroup$ Are you interested in an upper bound for all NFA or in methods to determing the number of states given an NFA? $\endgroup$
    – Raphael ♦
    Oct 31, 2016 at 19:16
  • $\begingroup$ @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. $\endgroup$
    – Garrick
    Nov 1, 2016 at 2:41

1 Answer 1

Reset to default
1
$\begingroup$

The set of final states in the DFA that results from the subset construction is given by

$$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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ That is the worst-case, but we would expect that usually most of those states are dead, i.e. don't appear in the final automaton. $\endgroup$
    – Raphael ♦
    Oct 31, 2016 at 16:24
  • $\begingroup$ Yes, but a precise estimate will depend on the NFA under consideration. $\endgroup$
    – Hans Hüttel
    Oct 31, 2016 at 16:26
  • $\begingroup$ Of course. I understand the question to ask for determining the number given an NFA. $\endgroup$
    – Raphael ♦
    Oct 31, 2016 at 19:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.