Skip to main content
3 of 3
edited body; edited title
D.W.
  • 165.6k
  • 21
  • 230
  • 490

NFA with exponential number of states when determinized

How can I build an example of a regular language where the minimal DFA has $2^n$ states and the minimal NFA has $n$ states? Obviously the DFA's state-set should contain all subsets of the the NFA's state-set, but I don't know how to start. Any suggestions to put me on the right track?

mrk
  • 3.7k
  • 23
  • 35