Find a DFA that accepts words with "aa" twice

In summary, the conversation is about a person who is learning about DFA's and is struggling with solving a problem involving the input alphabet Σ = {a,b}. They have attached their attempts so far, but are unsure of what to do with the words in state 2 that have a b*a*b* substring before getting their second "aa". They ask for help and clarify that the DFA accepts the string "aaa" because it contains the substring "aa" twice. There is also a question about the states 4 and 0 and their respective meanings, as well as a suggestion that the input "abaaa" may require a new state.
  • #1
tomkoolen
40
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: 588
Physics news on Phys.org
  • #2
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.
 

Related to Find a DFA that accepts words with "aa" twice

What does "Find a DFA that accepts words with "aa" twice" mean?

This means finding a Deterministic Finite Automaton (DFA) that recognizes or accepts strings or words with the sequence "aa" appearing twice in them.

What is a DFA?

A DFA, or Deterministic Finite Automaton, is a finite state machine that recognizes or accepts a set of strings or words based on a specific set of rules.

How do you find a DFA that accepts words with "aa" twice?

To find a DFA that accepts words with "aa" twice, you can use the process of constructing a DFA using regular expressions. First, construct a regular expression that represents words with "aa" appearing twice. Then, convert the regular expression to a DFA using the steps of the construction process.

Why is it important to find a DFA that accepts words with "aa" twice?

Finding a DFA that accepts words with "aa" twice is important because it allows us to recognize or accept a specific set of strings or words that follow a certain pattern. This can be useful in various applications such as text processing, pattern matching, and language recognition.

Can a DFA accept words with "aa" appearing twice in any position?

Yes, a DFA can be constructed to accept words with "aa" appearing twice in any position. However, the construction process may vary depending on the specific position or conditions of the "aa" sequence in the words.

Similar threads

Are These Computer Science Languages Regular?
    • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
Inductively define language a, b, aa, bb, aaa, bbb, ....
    • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
Engineering Current density calculation in anisotropic ferromagnetic film
    • Engineering and Comp Sci Homework Help
Replies
7
Views
1K
Oscillation of free surface of water in parallelepiped container
    • Introductory Physics Homework Help
Replies
13
Views
886
Which MSc to do after BSc physics if you love to code?
    • STEM Academic Advising
Replies
10
Views
2K
Destructive interference - What happens to the energy?
    • Quantum Physics
Replies
20
Views
5K
The Secrets of Prof. Verschure's Rosetta Stones
    • Earth Sciences
2
Replies
63
Views
8K
A Quantum nonlocality and "spooky action at a distance"
    • Quantum Interpretations and Foundations
4
Replies
139
Views
6K
Quantum Panda: Exploring the Intersection of Physics and Quantum Computing
    • New Member Introductions
Replies
1
Views
202
Other Computer Science Career Path Help
    • STEM Career Guidance
Replies
1
Views
2K

Hot Threads

Recent Insights

Back
Top