Skip to main content
Computer Science

Return to Question

edited body; edited title
Source Link
D.W. ♦
D.W. ♦
  • 165.6k
  • 21
  • 230
  • 490

NFA with exponential number of states when deteminizeddeterminized

How can I build an example of a regular language where the minimal DFA that has $2^n$ states whereand the equivalentminimal 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?

NFA with exponential number of states when deteminized

How can I build an example of a DFA that has $2^n$ states where the equivalent 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?

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?

Tweeted twitter.com/#!/StackCompSci/status/241913935111012352
edited tags; edited tags
Link
Raphael
Raphael
  • 72.9k
  • 30
  • 181
  • 393
Source Link
mrk
mrk
  • 3.7k
  • 23
  • 35

NFA with exponential number of states when deteminized

How can I build an example of a DFA that has $2^n$ states where the equivalent 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?