Deterministic Finite State Automaton Construction

Click For Summary
SUMMARY

The discussion centers on constructing a Deterministic Finite Automaton (DFA) that accepts natural numbers divisible by 3. The key insight is that a number is divisible by 3 if the sum of its digits is divisible by 3. The participant initially struggled with applying this concept but ultimately resolved the problem, indicating successful comprehension of the DFA construction process.

PREREQUISITES
  • Understanding of Deterministic Finite Automata (DFA)
  • Knowledge of modular arithmetic, specifically mod 3
  • Familiarity with checksum calculations for digit sums
  • Basic principles of automata theory
NEXT STEPS
  • Study the construction of DFAs for different modular conditions
  • Explore the relationship between digit sums and divisibility rules
  • Learn about state transition diagrams for DFAs
  • Investigate applications of DFAs in lexical analysis and pattern matching
USEFUL FOR

Students in computer science, particularly those studying automata theory, as well as educators and professionals involved in algorithm design and computational theory.

francis21
Messages
8
Reaction score
0

Homework Statement


Find a simple DFA (i.e. deterministic finite automaton) that accepts all natural numbers n for which n mod 3 = 0.

Hint: A natural number is divisible by 3 if its checksum (or sum of digits) is divisible by 3.


Homework Equations





The Attempt at a Solution



I'm not sure how the hint can help for this question, even though I know what it means. For instance, 137 = 1+3+7 = 11 mod 3 ≠ 0 etc.

Any other useful hints or suggestions would be great. Thanks. :)
 
Physics news on Phys.org
I have finally solved the problem, so its all good now.

Can the admin close this thread down. Thanks.
 

Similar threads

Transition Diagrams and finite-state automaton?
  • · Replies 3 ·
Replies
3
Views
2K
MHB Designing a Deterministic Finite Automaton for Binary Input and Output Sequences
  • · Replies 12 ·
Replies
12
Views
3K
How Does This Pascal Code Validate a Business Registration Number?
  • · Replies 3 ·
Replies
3
Views
3K
Comp Sci RSA to encrypt English Alphabets, any restrictions?
  • · Replies 7 ·
Replies
7
Views
2K
FSM that only accepts strings w/ equal number of 1's and 0's
  • · Replies 1 ·
Replies
1
Views
2K
Graduate About a natural extension of Collatz conjecture
  • · Replies 3 ·
Replies
3
Views
1K
Pascal - absolute sum of digits
  • · Replies 4 ·
Replies
4
Views
3K
Pascal - sum of digits in binary/hexadecimal
  • · Replies 2 ·
Replies
2
Views
3K
Question about O(log n) algorithm for computing a^n
  • · Replies 1 ·
Replies
1
Views
1K
Factor the repunit ## R_{6}=111111 ## into a product of primes
  • · Replies 3 ·
Replies
3
Views
2K