deterministic finite automaton

a finite automaton is a 5-tuple , where
  1. is a finite set called the states,
  2. is a finite set called the alphabet,
  3. is the transition function,
  4. is the start state, and
  5. is the set of accept states.
[cite:;taken from @sipser_comp_2012 definition 1.5]
a configuration of a finite automaton is an element of . the current configuration of an automaton is a pair
[cite:@goldberg_automata]
given a DFA ,
for configurations such that , we write iff .
for configurations , where , and we write iff there exist where such that .
if then iff .
[cite:@lewenstein_automata]
a DFA accepts a string if for .
[cite:@lewenstein_automata]
given a DFA , we denote by the language of all words that accepts:
we say recognizes the language . and call a regular language.
[cite:@lewenstein_automata]
let be a finite automaton and let be a string where each is a member of the alphabet , then accepts if a sequence of states in exists with three conditions:
  1. ,
  2. , for , and
  3. .
condition 1 says that the machine starts in the start state. condition 2 says that the machine goes from state to state according to the transition function. condition 3 says that the machine accepts its input if it ends up in an accept state. we say that recognizes language if .
[cite:@sipser_comp_2012]
[cite:@sipser_comp_2012 chapter 1.1 designing finite automata] describes how to build automata in detail.
a string input starts at , if we detect an , we move forward to the state which represents a progress of 1 in detecting 3 occurrences of , if the next character is in , our progress would be cancelled and we go back to , otherwise we move to , if we detect a we move to the accept state and stay there since we've achieved our goal of detecting 3 's, otherwise we "cancel our progress" and go back to .
at first glance this may seem impossible because DFA's cant tell the length of the string and have no record of its symbols, but it can "store" knowledge in the form of states.
here is my line of reasoning for this problem:
the possible states for this problem are
  1. string length is 1, so the DFA shouldnt accept, that is the state
  2. second-to-last seen symbol was , and the current symbol is , we should accept
  3. second-to-last seen symbol was , and the current symbol is , we should accept
  4. second-to-last seen symbol was , and the current symbol is , we shouldnt accept
  5. second-to-last seen symbol was , and the current symbol is , we shouldnt accept
states 4 and 5 cannot be unified into a single non-accepting state that says "last symbol wasnt " because if we're currently at a state that says "last symbol wasnt ", we cant know what the character is, we just know that before it there wasnt an , and so we wouldnt know where to move from there, this might not make much sense for the reader as its merely someone else's thoughts put into few words, so perhaps it helps to consider an automaton that unifies those states into one, how would it behave for the input string ?
states 2 and 3 also cant be unified into a single accepting state, because the automaton needs to be able to tell the difference between those states to decide whether it should accept the sequence , for example.
this hints that we need a total of 4 states (2 accepting, 2 non-accepting) beside the initial state, but perhaps we can reuse the initial state and unify it with state 4 or 5.