Regular Languages

Regular expression

Definition: A regular expression is recursively defined as follows.

1. Φ is a regular expression denoting an empty language.
2. ϵ(epsilon) is a regular expression indicates the language containing an empty string.
3. a is a regular expression which indicates the language containing only {a}
4. If R is a regular expression denoting the language L_R and S is a regular expression denoting the language L_S, then
   1. R+S is a regular expression corresponding to the language L_RUL_S.
   2. R.S is a regular expression corresponding to the language L_R.L_S..
   3. R* is a regular expression corresponding to the language L_R^*.
5. The expressions obtained by applying any of the rules from 1-4 are regular expressions.
   

The table shows some examples of regular expressions and the language corresponding to these regular expressions.

Regular expressions	Meaning
(a+b)*	Set of strings of a’s and b’s of any length including the NULL string.
(a+b)*abb	Set of strings of a’s and b’s ending with the string abb
ab(a+b)*	Set of strings of a’s and b’s starting with the string ab.
(a+b)*aa(a+b)*	Set of strings of a’s and b’s having a sub string aa.
a*b*c*	Set of string consisting of any number of a’s(may be empty string also) followed by any number of b’s(may include empty string) followed by any number of c’s(may include empty string).
a+b+c+	Set of string consisting of at least one ‘a’ followed by string consisting of at least one ‘b’ followed by string consisting of at least one ‘c’.
aa*bb*cc*	Set of string consisting of at least one ‘a’ followed by string consisting of at least one ‘b’ followed by string consisting of at least one ‘c’.
(a+b)* (a + bb)	Set of strings of a’s and b’s ending with either a or bb
(aa)*(bb)*b	Set of strings consisting of even number of a’s followed by odd number of b’s
(0+1)*000	Set of strings of 0’s and 1’s ending with three consecutive zeros(or ending with 000)
(11)*	Set consisting of even number of 1’s

                              Meaning of regular expressions

Obtain a regular expression to accept a language consisting of strings of a’s and b’s of even length.

String of a’s and b’s of even length can be obtained by the combination of the strings aa, ab, ba and bb. The language may even consist of an empty string denoted by ϵ. So, the regular expression can be of the form

(aa + ab + ba + bb)*

The * closure includes the empty string.
Note: This regular expression can also be represented using set notation as

L(R) = {(aa + ab + ba + bb)ⁿ | n >= 0}

Obtain a regular expression to accept a language consisting of strings of a’s and b’s of odd length.

String of a’s and b’s of odd length can be obtained by the combination of the strings aa, ab, ba and bb followed by either a or b. So, the regular expression can be of the form

(aa + ab + ba + bb)* (a+b)

String of a’s and b’s of odd length can also be obtained by the combination of the strings aa, ab, ba and bb preceded by either a or b. So, the regular expression can also be represented as

(a+b) (aa + ab + ba + bb)*

Note: Even though these two expression are seems to be different, the language corresponding to those two expression is same. So, a variety of regular expressions can be obtained for a language and all are equivalent.