Find a DFA that accepts words with "aa" twice

Click For Summary
SUMMARY

The discussion focuses on constructing a Deterministic Finite Automaton (DFA) that accepts strings containing the substring "aa" at least twice over the alphabet Σ = {a, b}. The user is grappling with the transitions between states, particularly how to handle substrings that include "b" while still ensuring the second occurrence of "aa" is recognized. It is clarified that the string "aaa" is accepted due to containing "aa" twice, while "abaaa" is not accepted, indicating the importance of state transitions in the DFA design.

PREREQUISITES
  • Understanding of Deterministic Finite Automata (DFA)
  • Familiarity with state transition diagrams
  • Knowledge of string patterns and substrings
  • Basic concepts of formal languages and automata theory
NEXT STEPS
  • Study the construction of DFAs for specific string patterns
  • Learn about state minimization techniques in DFAs
  • Explore the implications of substrings on state transitions
  • Review examples of DFAs that accept multiple occurrences of substrings
USEFUL FOR

This discussion is beneficial for students and educators in computer science, particularly those studying automata theory, as well as software developers working with pattern recognition and state machine implementations.

tomkoolen
Messages
39
Reaction score
1
Hi everyone,

I have just started learning about DFA's and I have to solve the problem from the thread title with
Σ = {a,b}.

My attempts so far are in the attachments.

I am struggling as to what to do with the words in state 2 that have a b*a*b* substring before getting their second "aa". Can anyone help me with this?

NB: It was noted in the exercise that "aaa" is accepted by the DFA because it contains the substring "aa" twice as well.
 

Attachments

  • DFA.jpg
    DFA.jpg
    14.6 KB · Views: 639
Physics news on Phys.org
Why do you have 4 and 0 and where is the difference between those states? What do they mean?
"abaaa" does not get accepted like that.

2b will need a new state I think.
 

Similar threads

Engineering Current density calculation in anisotropic ferromagnetic film
  • · Replies 7 ·
Replies
7
Views
2K
Destructive interference - What happens to the energy?
  • · Replies 20 ·
Replies
20
Views
6K
Oscillation of free surface of water in parallelepiped container
  • · Replies 13 ·
Replies
13
Views
2K
Which MSc to do after BSc physics if you love to code?
  • · Replies 10 ·
Replies
10
Views
3K
Testing C & Python Resources for Problems in Astrophysics for upcoming CS Exam
  • · Replies 6 ·
Replies
6
Views
2K
Help with terminal project in Mac
  • · Replies 1 ·
Replies
1
Views
2K
Considering Switching from Physics to Computer Engineering
  • · Replies 7 ·
Replies
7
Views
2K
I want to work with NASA Spacecraft like Voyager
  • · Replies 1 ·
Replies
1
Views
2K
Write a function that will find a temperature....
  • · Replies 6 ·
Replies
6
Views
2K
Graduate Quantum nonlocality and "spooky action at a distance"
  • · Replies 140 ·
5
Replies
140
Views
12K