The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+13 votes
2.1k 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!$
asked in Theory of Computation by Veteran (68.8k points)
edited by | 2.1k views

4 Answers

+22 votes
Best answer
ans 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).
answered by Boss (8.4k points)
selected by
+8 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
answered by Veteran (48.5k points)
0 votes

Answer is B. i.e., 2N

answered by Loyal (2.6k points)
–1 vote
Ans: B
answered by Boss (7.4k points)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

32,503 questions
39,217 answers
109,114 comments
36,599 users