How a DFA Processes Strings The rst thing we need to understand about aDFA is how the DFA
decides whether or not to accept a sequence of input symbols The language of the DFA is the set of all
strings that the DFA accepts Suppose aa an is a sequence of input symbolsWe start out with the DFA
in its start state q We consult the transition function say q a q to nd the state that the DFA A enters
after processing the rst input symbol a We process the next input symbol a by evaluating q a let us
suppose this state is q We continue in this manner nding states q q q n suchthat qi ai qi for each i If qn
is a member of F then the input aa if not then it is rejected Example an is accepted and Let us formally
specify a DFA that accepts all and only the strings of s and s that have the sequence can write this
language L as somewhere in the string We fw j w is of the form x y for some strings x and y
consisting of s and s onlyg Another equivalent description using parameters x and y to the left of the
vertical bar is fx yjx and y are any strings of s and sg Examples of strings in the language include of
strings not in the language include and and Examples What do we know about an automaton that can
accept this language L First its input alphabet is f g Ithas some set of states Qo fwhich one say q is the
start state This automaton has to remember the important facts about what inputs it has seen so far To
decide whether of the input A needs to remember is a substring More accurately the graph is a picture
of some transition function and the arcs of the graph are constructed to re ect the transitions speci ed
by DETERMINISTIC FINITE AUTOMATA Has it already seen If so then it accepts every sequence
of further inputs ie it will only be in accepting states from nowon Has it never seen it will have seen
Has it never seen but its most recent inputwas so if it now sees a and can accept everything it sees
from here on but its last input was either nonexistent it just started or it last sawa In this caseA cannot
accept until it rstsees a andthen sees a immediately after These three conditions can each be
represented by a state Condition is represented by the start state q Surelywhen just starting we need to
see a and then a But if in state q we next see a then we are no closer to seeing and so wemust stay in
state q That is q q However if we are in state q and we next see a we are in condition That is we have
never seen represent condition but we have our Thus let us use q to Our transition from q on input is q
q Now let us consider the transitions from state q If weseea w eareno better o than wewere but no
worse either Wehave not seen but was thelastsymbol so we are still waiting for a State q describes this
situation perfectlys owewant q q If we are in state q and weseea input we nowknow there is a
followed by a We can go to an accepting state whichwe shall call q and which corresponds to
condition q q above That is Finallyw emust design the transitions for state q In this state wehave
already seen a sequence so regardless of what happens we shall still be in a situation where weve seen
That is q q q Thus Q fq q qg As we said q is the start state and the only accepting state is q that is F
fqg The complete speci cation of the automaton A that accepts the language L of strings that have a is
A fq q qgf g q fqg where is the transition function described above