search
Log In
20 votes
6k views

Given an arbitrary non-deterministic finite automaton (NFA) with $N$ states, the maximum number of states in an equivalent minimized DFA at least

  1. $N^2$
  2. $2^N$
  3. $2N$
  4. $N!$
in Theory of Computation
edited by
6k views
0
if NFA has $N$ states then DFA can have  $M$ states where $1\leq M \leq 2^N$

4 Answers

31 votes
 
Best answer

Answer is (B) $2^N$.

In DFA any subset of the $N$ states (for $N$ element set $2^N$ subsets possible)  can become a new state and they can remain even when the DFA is minimized. So, maximum we can get $2^N$ states for the minimized DFA. (at least in question must be a typo for at most).


edited by
0

In DFA any subset of the N states

 This should be "In NFA any subset of the N states..."

9 votes
Answer is 2^N.

Example DFA-> 3rs symbol from right is x.

https://gateoverflow.in/544/gate1991_17-b

Here you have to use 2^3 symbols.

nth symbol from right is x , this DFA will have 2^n state.s
0 votes

Answer is B. i.e., 2N

0 votes
Ans: B
Answer:

Related questions

25 votes
4 answers
1
7.1k views
Consider a DFA over $\Sigma=\{a,b\}$ accepting all strings which have number of a's divisible by $6$ and number of $b$'s divisible by $8$. What is the minimum number of states that the DFA will have? $8$ $14$ $15$ $48$
asked Sep 14, 2014 in Theory of Computation Kathleen 7.1k views
23 votes
2 answers
2
1.6k views
Construct DFA's for the following languages: $L=\left\{w \mid w \in \{a,b\}^*, \text{ w has baab as a substring } \right\}$ $L=\left\{w \mid w \in \{a,b\}^*, \text{ w has an odd number of a's and an odd number of b's } \right\} $
asked Sep 15, 2014 in Theory of Computation Kathleen 1.6k views
20 votes
2 answers
3
4.1k views
Which of the following statements is true? If a language is context free it can always be accepted by a deterministic push-down automaton The union of two context free languages is context free The intersection of two context free languages is a context free The complement of a context free language is a context free
asked Sep 14, 2014 in Theory of Computation Kathleen 4.1k views
17 votes
2 answers
4
3.1k views
Consider the following two statements: $S_1: \left\{ 0^{2n} \mid n \geq 1 \right\}$ is a regular language $S_2: \left\{0^m1^n0^{m+n} \mid m \geq 1 \text{ and } n \geq 1 \right\}$ is a regular language Which of the following statement is correct? Only $S_1$ is correct Only $S_2$ is correct Both $S_1$ and $S_2$ are correct None of $S_1$ and $S_2$ is correct
asked Sep 14, 2014 in Theory of Computation Kathleen 3.1k views
...