snippetMinor
How to handle dfa with countless states?
Viewed 0 times
dfahandlewithstateshowcountless
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#87874, answer score: 3
Revisions (0)
No revisions yet.