Regular Languages
Every finite automaton accepts some language. If we consider all possible finite
automata, we get a set of languages associated with them. We will call such a set
of languages a family. The family of languages that is accepted by deterministic
finite accepters is quite limited. The structure and properties of the languages in
this family will become clearer as our study proceeds; for the moment we will
simply attach a name to this family.
Definition 2.3
A language L is called regular if and only if there exists some deterministic
finite accepter M such that
L= L(M).
Example 2.5
Show that the language is regular.
L= {awa: w ∈ {a,b} * }
To show that this or any other language is regular, all we have to do is find a
dfa for it. The construction of a dfa for this language is similar to Example 2.3,
but a little more complicated. What this dfa must do is check whether a string
begins and ends with an a; what is between is immaterial. The solution is
complicated by the fact that there is no explicit way of testing the end of the
string. This difficulty is overcome by simply putting the dfa into a final state
whenever the second a is encountered. If this is not the end of the string, and
another b is found, it will take the dfa out of the final state. Scanning continues
in this way, each a taking the automaton back to its final state. The complete
solution is shown in Figure 2.6. Again,
Figure 2.6