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.