Is Another State Required for This DFA?

AI Thread Summary
The discussion centers on creating state diagrams for deterministic finite automata (DFAs) that recognize strings of length at least three, with the third symbol being '0', using the alphabet {0,1}. Participants question the efficiency of their solutions and whether the number of states is optimal. It is noted that at least three states are necessary to track the first three characters of the input. Additionally, the need for a fourth state is argued, as none of the first three states can be accepting states, necessitating an accepting state for the DFA. The conversation emphasizes the importance of accurately representing the required states to ensure correct language recognition.
Opso
Messages
1
Reaction score
0

Homework Statement



Give state diagrams of DFAs recognizing the following languages. In all parts the alphabet is {0,1}.

{w | w has length at least 3 and its third symbol is a 0}

Homework Equations



If the final state only has one circle it is rejected, if two, accepted.

The Attempt at a Solution



aqr05.jpg


I am just wondering if this is the most efficient way of doing this problem, or do I have too many states?

Oh also, I forgot to add an arrow pointing to qs indicating the start.
 
Last edited:
Physics news on Phys.org
I think you'll agree that there may not be less than three states because one needs to track how much of the input has been seen. The only way to do this is to have independent states for the first three characters. Only on the third character may we check for the final 0.

Is another state required? See if you can you argue that because an accepting state is required, and because none of the first three states may be accepting states, a fourth state is necessary.
 
Back
Top