DFA that accepts either ab or ba as substring?

In summary, a DFA (Deterministic Finite Automaton) is a mathematical model that recognizes patterns and determines if a given input string belongs to a specific language. It consists of a finite set of states, input symbols, a transition function, a start state, and one or more accept states. To accept a substring, the DFA processes a part of the input string that matches the specified pattern. The minimum number of states required for a DFA to accept either "ab" or "ba" as substrings is three, including an initial state, a state for "a" transitions, and a state for "b" transitions. The accept states can be the same or different, depending on the desired acceptance of both "ab" and "ba
  • #1
shivajikobardan
674
54
Homework Statement
I need to create a DFA that contains substrings either ab or ba
Relevant Equations
Deterministic finite automata no equations
Attempt at solution-:

1635769064071.png

Now this dfa will also accept abba which in my inituition it should not accept. But it does accept it. What is going here? Please guide
 
Physics news on Phys.org
  • #2
The English language statement "contains either the substrings ab or ba" is the issue. If you read this as an "inclusive or" then your DFA looks okay. If you read it as an "exclusive or" then it is not okay. Since you are a student and you recognize this potential ambiguity, figure out the "exclusive or" case. Submit both variations and your professor will be delighted!

Is the alphabet { a, b } ?
 
Last edited:

FAQ: DFA that accepts either ab or ba as substring?

1. What is DFA that accepts either ab or ba as substring?

DFA stands for Deterministic Finite Automaton, which is a mathematical model used to recognize patterns in strings of characters. In this case, the DFA is designed to accept strings that contain either "ab" or "ba" as a substring.

2. How does a DFA accept either ab or ba as substring?

The DFA has a set of states and transitions between those states based on the input characters. It starts at the initial state and reads each character of the input string, following the transitions until it reaches an accepting state. In this case, the DFA would accept the string if it contains either "ab" or "ba" as a substring.

3. Can a DFA accept both "ab" and "ba" as substrings?

Yes, a DFA can accept both "ab" and "ba" as substrings if it has transitions for both patterns. The DFA would have two accepting states, one for each substring, and the transitions would lead to the corresponding accepting state depending on the input characters.

4. Is a DFA the only way to recognize strings with "ab" or "ba" as substrings?

No, there are other models such as Non-Deterministic Finite Automaton (NFA) or Regular Expressions that can also recognize patterns in strings. However, DFA is a commonly used and efficient model for this type of problem.

5. How can I design a DFA that accepts either ab or ba as substring?

To design a DFA for this problem, you would need to define the states, transitions, and accepting states based on the input alphabet and the desired substrings. It would involve careful consideration of the possible combinations of input characters and their corresponding transitions. You can also use tools such as state diagrams or regular expressions to aid in the design process.

Similar threads

Find a DFA that accepts words with "aa" twice
Replies
1
Views
1K
Proof that its possible to generate NFA from DFA
Replies
1
Views
2K
Comp Sci IEEE-754 Precision Format
Replies
17
Views
1K
Are These Computer Science Languages Regular?
Replies
1
Views
2K
Which Comp Sci Degree Should I Choose for Better Earnings?
Replies
3
Views
2K
Admissions Is it realistic to go from an undeclared major to a comp sci major?
Replies
20
Views
3K
Comp Sci Is VPN all about encapsulating the source and destination IP address?
Replies
2
Views
1K
Preparing for Physics Grad School after Math/Comp Sci undergrad
Replies
8
Views
2K
A Quantum nonlocality and "spooky action at a distance"
4
Replies
139
Views
8K
Comp Sci Errors during executing the program (Compaq Visual Fortran)
Replies
5
Views
2K

Hot Threads

Recent Insights

Back
Top