DHARM258 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE⇒ (2n + m) < | u. v^2. w | < (2n + m) + n ;
[to make equal, number of 0’s and 2’s add more n 2’s on right side of equality]
⇒ (2n + m) < | u. v^2. w | < (2n + m) + n + n ; [for 2n 0’s and 2n 2’s]
⇒ (2n + m) < | u. v^2. w | < [2(2n) + m]
That we see from the right side of equality, string | u. v^2. w | ≠ 4 n + m
⇒ u. v^2. w ∉ L
Hence language is not regular.10.4 Properties of Regular Languages...................................................................................
As we said earlier there are some inherent characterizations of a language if it is regular.
These inherent characterizations we summarize here as the properties of regular languages,
equally says the properties of regular expressions.
Among these properties:
l Regular expressions are closed under ∪ operation
l Regular expressions are closed under concatenation operation
l Regular expressions are closed under Complementation
l Regular expressions are closed under ∩ operation
l Regular expressions are closed under Subtraction operation
l Regular expressions are closed under H operation (Kleeny Closure)
Regular expression are closed under ∪ operation
This property says that the union of regular expressions is a regular expression. If r 1 and r 2
are two regular expressions and there languages are L(r 1 ) and L(r 2 ) then, union of r 1 and r 2 is
given as (r 1 + r 2 ) means either r 1 or r 2 , that is a regular expression.
It denotes the language L (r 1 + r 2 ); which is the language denoted by L (r 1 ) or language
denoted by L (r 2 ). This is a regular language in either case.
Or we say,
L(r 1 + r 2 ) = L(r 1 ) ∪ L(r 2 )
Hence, Regular languages are closed under union.
Regular expressions are closed under concatenation operation
Concatenation of regular expressions are a regular expression. If r 1 and r 2 are two regular
expressions and there languages are L(r 1 ) and L(r 2 ) then concatenation of r 1 and r 2 is given as,
(r 1. r 2 ) means regular expression r 1 followed by regular expression r 2. That results a regular
expression.
Now, the language of composite of regular expression (r 1. r 2 ) is L(r 1. r 2 ), that must be
language of r 1 followed by the language of r 2 , which is again a regular language.
i.e., L(r 1. r 2 ) = L(r 1 ). L(r 2 )
Hence Regular languages are closed under concatenation.
Regular expression is closed under complementation operation
The property says that complement of the regular expression is a regular expression. Let r is
a regular expression and it denotes the regular language L (i.e. L = L(r))