trace a few examples to see why this works. After one or two tests, it will be
obvious that the dfa accepts a string if and only if it begins and ends with an a.
Since we have constructed a dfa for the language, we can claim that, by
definition, the language is regular.
Example 2.6
Let L be the language in Example 2.5. Show that L 2 is regular. Again we show
that the language is regular by constructing a dfa for it. We can write an explicit
expression for L 2 , namely,
Therefore, we need a dfa that recognizes two consecutive strings of essentially
the same form (but not necessarily identical in value). The diagram in Figure 2.6
can be used as a starting point, but the vertex q 3 has to be modified. This state
can no longer be final since, at this point, we must start to look for a second
substring of the form awa. To recognize the second substring, we replicate the
states of the first part (with new names), with q 3 as the beginning of the second
part. Since the complete string can be broken into its constituent parts wherever
aa occurs, we let the first occurrence of two consecutive a’s be the trigger that
gets the automaton into its second part. We can do this by making δ(q 3 ,a)= q 4 .
The complete solution is in Figure 2.7. This dfa accepts L 2 , which is therefore
regular.
Figure 2.7