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?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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