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 $r$ and $s$, $rs$ represents the set of all strings that may be obtained by concatenating strings of $r$ with strings of $s$ and $r{\tt \vert}s$ represents the union of $r$ and $s$; in addition, for any set $s$, $s^*$ represents the set of all strings that may be obtained by concatenating strings of $s$ to themselves zero (that is, the empty string $\epsilon$) 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 $\emptyset$), the languages containing a single one-symbol string ($\{\sigma\}$ for all $\sigma \in \Sigma$, represented simply by $\sigma$), and the language containing only the empty string $\{\epsilon\}$ (represented by $\epsilon$ 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.