3
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

You seem to have missed the last sentence of the question:

What is the problem with this DFA?

The problem with this DFA is that it isn't finite (so it's not really a DFA).

A DFA is a static object — the only way it interacts with the environment is by switching states.

$\endgroup$
  • $\begingroup$ But if the input is finite, then wouldn't the sum be technically finite also? $\endgroup$ – Robur_131 Feb 8 '18 at 20:12
  • $\begingroup$ Every natural number is finite. The set of natural numbers is infinite. $\endgroup$ – Yuval Filmus Feb 8 '18 at 20:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.