-1
$\begingroup$

I am attempting to draw the DFA of this problem but I'm kind of stuck. In another post I saw that the DFA should have 10 states. I'm finding it hard to even understand the question, is the input to the DFA the full string so for example 1001 or is it multiple inputs of length 3 in this example 100 and then 001. I've made multiple DFA's now but they all seem incorrect to me. Below is my latest attempt which doesn't seem to work for me. Since when trying the string 1001 it goes to an accepting state but the last 1 puts it back into a non accepting state. I'm really struggling with checking for every substring of length 3 since you leave the final state when you have a length which is not a multiple of 3, but it should still be accepted. How would I make a DFA that accepts strings of minimal length 3 but then also of length 4 which satisfies these conditions? (I know the DFA is not yet fully finished) I have created a dead state for whenever a string has 2 1's within a substring of length 3.

Thanks! enter image description here

EDIT: The last DFA is correct :)

enter image description here

$\endgroup$
1

2 Answers 2

0
$\begingroup$

An automaton should come with a plan. What is stored or represented in each of the states?

When the requirement asks us to check all substrings of a certain length the plan might start with a substring automaton that keeps in its state the last $k$ symbols seen. A window, sliding over the input string. Below an example for $k=3$. From state $xyz$ after reading $a$ we move to state $yza$.

substring automaton

In the current question all states should contain two or more $0$'s. That means that all four states to the right fail, and can be lumped together to form a garbage state. There are no longer outgoing states from the garbage back to the four states at the left.

Initially the automaton has not read any symbols. That means we add initial states with less than three letters read, in the form of a tree. Any string shorter than $3$ should be trivially accepted (having no substrings of length $3$).

One finds this automaton in the context of De Bruijn sequences. Languages that can be recognized by a sliding window automaton are called locally testable.

$\endgroup$
0
$\begingroup$

You need seven states:

The error state - once in the error state you always go to the non-accepting error state.

States 00, 01, 10, 11: These are the last two characters processed. If we process 0 then we move from 00 or 10 to 00, from 01 to 10, and from 11 to error. (11 will only be encountered if the first two characters are 11). If we process a 1, we move from 00 to 01, and from the other states to error.

Now what do we do if no or one character have been processed: We add a start state and a state 1. From the start state we go to 00 or 1. From 1 we go to 10 or 11. All states except the error state are accepting.

$\endgroup$
1
  • $\begingroup$ My teacher already told me that the given graph is correct (the bottom one). It might be simplified but it does work so I'm happy (: $\endgroup$
    – Jellyfish
    Dec 5, 2023 at 20:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.