3

Wikipedia : Because DFAs can be reduced to a canonical form (minimal DFAs), there are also efficient algorithms to determine:

  • whether a DFA accepts any strings.
  • whether a DFA accepts all strings.
  • whether two DFAs recognize the same language.

I am not able prove how first two properties are decidable or by which algorithms we can determine same.

CodeLover
  • 185
  • Do you know the algorithm for minimizing a DFA? That is what Wikipedia is discussing here. After minimization, if the resulting DFA has all accepting states, it clearly accepts all strings; if it has no accepting states it clearly accepts no strings. – MJD Apr 29 '14 at 03:00
  • oh yes !! thank you :) – CodeLover Apr 29 '14 at 03:04
  • @MJD Because that seemed to help the OP, you could make that an answer... (ping me and I'll upvote to get this off the unanswered queue...) – apnorton Apr 29 '14 at 03:24

1 Answers1

4

Do you know the algorithm for minimizing a DFA? That is what Wikipedia is discussing here.

After minimization, if the resulting DFA has only one state, it either accepts every string, if its one state is an accepting state, or accepts no strings, if its one state is non-accepting.

MJD
  • 65,394
  • 39
  • 298
  • 580