Skip to main content
Tweeted twitter.com/StackCompSci/status/963023628144136192
fixed title
Link
Robur_131
  • 217
  • 3
  • 9

Question about DFA How to handle dfa with countless states?

edited tags
Link
Raphael
  • 72.9k
  • 30
  • 181
  • 393
Source Link
Robur_131
  • 217
  • 3
  • 9

Question about DFA

I have a question regarding DFA:

Design a DFA M with alphabet $\sum = \ {\{0,1,2,R}\}$ where the states remember actual sums of the number, except that the sum is reset to 0 whenever the symbol $R$ appears. Show diagrammatically how this DFA can be constructed. What is the problem with this DFA?

One thing I do understand is that in order to remember the actual sums I would have to have the sums as states. But sums can be any number from 0 to infinity. So would the states increase exponentially while reading the input string? How can I tackle this problem?