9 Regular Expressions
2129.1 INTRODUCTION TO REGULAR EXPRESSIONS
In the previous chapter we have studied that the power of a finite automaton is given by the
language it accepts, that contains finite or infinite many strings. So, Is there any convenient
way to express these set of strings. In this chapter we shall focus our attention to the descrip-
tion of a language by an algebraic expression called as regular expression. The operations
used in the formation of regular expressions are union, concatenation, and Kleeny closure.
The language generated by a regular expression is called regular language. Regular expres-
sions are capable to defining all and only the regular languages. The significance of the sym-
bols used to represent the regular expression is different than the symbol used to specify the
strings. So, we use bold symbols in representing the regular expressions while for the string
we uses the symbols as usual.
Regular language is the language depicted (expressed) by the regular expression.9.2 DEFINITION OF REGULAR EXPRESSION
Assume the set of alphabets S = {a 1 , a 2 , a 3 , .........an}, and r be a regular expression
defined over Σ and let the language generated by the regular expression r be L(r), then the
basis regular expressions are,
1.ai is the regular expression corresponding to the symbol ai ∈ Σ for ∀ i = 1 to n. The
language generated by regular expression ai will be L(ai) i.e.,
L(ai) = {ai}, for ∀ i = 1 to n.
2.∈∈∈∈∈ is a regular expression corresponding to the null string (∈), and the language
generated by the regular expression ∈∈∈∈∈ will be L(∈) i.e.,
L(∈∈∈∈∈) = {∈}.
3.ΦΦΦΦΦ is the regular expression corresponding to the nonexistence of any input symbol
and the language generated by the regular expression Φ will be L(Φ) i.e.,
L(ΦΦΦΦΦ) = Φ;
Above definition of regular expression can be extended further by defining its behavior
over set of operators union (+), concatenation (.), and Kleeny closure (*) i.e.,
- If r 1 and r 2 are two regular expressions, and their languages are L(r 1 ) and L(r 2 )
respectively, then (r 1 + r 2 ) will also be a regular expression and it generates the