search
Log In
0 votes
110 views

 

in Theory of Computation 110 views
0
How can one tell number of states in NFA from states of an arbitrary DFA
0
It's b
because a DFA is an NFA. So the states can remain to be the same.
0
@vikas @dharmendra @mk Utkarsh

Im not able to understand this concept.

Please explain.

As per my understanding in DFA, For N states there can be N transition so N states should be there and for NFA for N states there can be 2 ^N transition so 2^N states.

Please suggest
0

Mayankprakash ignore this question because they are not talking about minimal DFA

if they would have been talking about minimal DFA with $2^N$ states then states in the corresponding NFA can range between $N$ and $2^N$

from this information we can eliminate A and D

but then read the first line of this comment :p

0
@mk Utkarsh

if they would have been talking about minimal DFA with $2^N$ states then states in the corresponding NFA can range between $N$ and

How?

Please explain

1 Answer

0 votes
Every DFA can be NFA. If NFA have 'n' states then DFA have maximum 2^n states.

So option B is correct.

Power of NFA = Power of DFA

Related questions

0 votes
1 answer
1
184 views
When we convert a (minimal) NFA to DFA by subset construction method, is the DFA obtained always a minimal DFA? Please elaborate.
asked Nov 15, 2018 in Theory of Computation Mizuki 184 views
0 votes
1 answer
2
647 views
Every DFA is NFA but not vice versa Can you please explain how this statement is true? Reference:- https://www.geeksforgeeks.org/toc-finite-automata-introduction/
asked Aug 28, 2018 in Theory of Computation dan31 647 views
3 votes
1 answer
3
469 views
According to this Hopcroft's algorithm , we can efficiently minimize a Finite automata in $O(nlogn)$ time (polynomial time algo) then why it is said that Minimizing Finite Automata is computationally hard according to this link ?
asked Mar 27, 2018 in Theory of Computation ankitgupta.1729 469 views
...