Finite-state automata and regular languages

Each given DFA, as defined in eq. 2.3, can *accept* a
certain set of strings of symbols. A (finite or
infinite) set of strings over a given alphabet is
usually called a *language*. The class of languages that DFAs can
accept is called the class of *regular
languages*, where
the word *regular* is borrowed from
Kleene (1956)'s ``regular events''; in other
words, if a language is accepted by a DFA, it is a regular language,
and *vice versa*. These languages (also called *regular sets*)
may be represented by *regular
expressions* based on
Kleene (1956)'s regular events. Each
regular expression represents a set of strings. Now, for any two
expressions and , represents the set of all strings that
may be obtained by concatenating strings of with strings of
and represents the union of and ; in addition, for
any set , represents the set of all strings that may be
obtained by concatenating strings of to themselves zero (that is,
the empty string ) or more times (this operation is called
the Kleene closure and the symbol is called the
Kleene star); using these operations (concatenation, union, and Kleene
closure) on regular languages always yields regular languages. The basic regular
languages are the empty set (represented ), the
languages containing a single one-symbol string ( for all
, represented simply by ), and the language
containing only the empty string (represented by
itself). It is easy to show that any finite language is
regular. Kleene (1956) showed for the first time that the set of languages
expressible by regular
expressions
is
exactly the one that may be accepted by a net with
circles, that is, by a finite-state
machine (see also
Hopcroft and Ullman (1979, 218), Salomaa (1973, 27)).

See section 4.1.1 for an introduction to grammars as an alternative way of defining formal languages.