deterministic finite automaton
a finite automaton is a 5-tuple
, where
[cite:;taken from @sipser_comp_2012 definition 1.5]
[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]
for configurations
for configurations
if
[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]
[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:
recognizes language
if
.
[cite:@sipser_comp_2012]
-
,
-
, for
, and
-
.
[cite:@sipser_comp_2012]
[cite:@sipser_comp_2012 chapter 1.1 designing finite automata] describes how to build automata in detail.
here is my line of reasoning for this problem:
the possible states for this problem are
- string length is 1, so the DFA shouldnt accept, that is the state
- second-to-last seen symbol was
, and the current symbol is
, we should accept
- second-to-last seen symbol was
, and the current symbol is
, we should accept
- second-to-last seen symbol was
, and the current symbol is
, we shouldnt accept
- second-to-last seen symbol was
, and the current symbol is
, we shouldnt accept
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
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.