A
Chapter 3
Regular Languages and Regular Grammars
ccording to our definition, a language is regular if there exists a finite
accepter for it. Therefore, every regular language can be described by
some dfa or some nfa. Such a description can be very useful, for
example, if we want to show the logic by which we decide if a given
string is in a certain language. But in many instances, we need more
concise ways of describing regular languages. In this chapter, we look at other
ways of representing regular languages. These representations have important
practical applications, a matter that is touched on in some of the examples and
exercises.
3.1 Regular Expressions
One way of describing regular languages is via the notation of regular
expressions. This notation involves a combination of strings of symbols from
some alphabet Σ, parentheses, and the operators +, ., and *. The simplest case is
the language {a}, which will be denoted by the regular expression a Slightly
more complicated is the language {a, b, c}, for which, using the + to denote
union, we have the regular expression a+b+c. We use · for concatenation and *
for star-closure in a similar way. The expression (a + (b·c))* stands for the starclosure of {a} ∪; {b}, that is, the language {λ, a, bc, aa, abc, bca, bcbc, aaa,
aabc,…}.
Formal Definition of a Regular Expression
We construct regular expressions from primitive constituents by repeatedly
applying certain recursive rules. This is similar to the way we construct familiar
arithmetic expressions.
Definition 3.1
Let Σ be a given alphabet. Then