2 of 18

REGULAR EXPRESSION

Regular expressions describe regular languages

These are an algebraic representations of languages

Amity School of Engineering & Technology

3 of 18

Let Σ be an alphabet. The regular expressions over Σ and the sets that they denote are defined recursively as follows.

ϕ is a regular expression and denotes empty set
ε is a regular expression and denotes the set {ε}
For each ‘a’ in Σ, ‘a’ is a regular expression and denotes the set {a}
If ‘r’ and ‘s’ are regular expressions denoting the languages R and S respectively, then the regular expressions:

r + s denotes R U S

rs denotes RS

r* denotes R*

Amity School of Engineering & Technology

4 of 18

REGULAR EXPRESSION - operations

are regular expressions

Given regular expressions r₁ and r₂

Union

Concatenation

Star Closure

Amity School of Engineering & Technology

5 of 18

Amity School of Engineering & Technology

6 of 18

REGULAR EXPRESSION - example

A regular expression:

Not a regular expression:

Amity School of Engineering & Technology

7 of 18

Equivalence of Regular Expressions - example

= { all strings without two consecutive 0 }

and

are equivalent regular expr.

L (r₁) = { ε, 0, 1, 10, 01, 11, 110, 0101,…. }

L (r₂) = { ε, 0, 1, 10, 01, 11, 110, 0101,…. }

Amity School of Engineering & Technology

8 of 18

Equivalence of Regular Expressions

Regular expressions and

are equivalent if

Amity School of Engineering & Technology

9 of 18

Identity Rules for Regular Expression

The two regular expression’s P and Q are equivalent (denoted as P=Q) if and only if P represents the same set of strings as Q does.

For showing the equivalence of two regular expressions we need to show some identities of regular expression’s

Amity School of Engineering & Technology

10 of 18

Identity Rules for Regular Expression

εR=R ε=R
ε* = ε
(Φ)* = ε
ΦR = RΦ = Φ
Φ + R = R
R + R = R
RR* = R*R = R⁺
(R*)* = R*

Ε + RR* = R*
(P + Q)R = PR + QR
(P + Q)* = (P*Q*)* = (P* + Q*)*
R*(ε + R) = ( ε + R)R* = R*
(R + ε)* = R*
Ε + R* = R*
(PQ)*P = P(QP)*
R*R + R = R*R

Amity School of Engineering & Technology

11 of 18

Amity School of Engineering & Technology

12 of 18

Amity School of Engineering & Technology

13 of 18

Amity School of Engineering & Technology

14 of 18

Language & REGULAR EXPRESSION

All strings of 0’s and 1’s starting with 0 and ending with 1: 0(0+1)*1
All strings of 0’s and 1’s with even number of 0’s : 1 * (01*01* ) *
All strings of 0’s and 1’s with at least two consecutive 0’s: (0+1)*00 (0+1)*

Amity School of Engineering & Technology

15 of 18

REGULAR EXPRESSION & Language

Regular Expression	Language
0*	Set of all strings of the form 0ⁿ (n>=0) L = {ε, 0, 00, 000, 0000, 00000, . . . }
1+0	Set of 0 and 1 L = { 0, 1 }
01	L = { 01 }
(01)*	Set of all strings containing n ‘01’s ( n >= 0 ) L = {ε , 01, 0101, 010101, 01010101, . . . }
(1+0)*	Set of all strings containing 1 and 0 L = {ε, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, …. }
01*	Set of all strings start with 0 followed by n 1s ( n>=0 ) L = { 0, 01, 011, 0111, 01111, 011111, … }
(0+1)00	L = {000, 100}

Amity School of Engineering & Technology

16 of 18

More Examples

Write the regular expression for the language accepting all the string which are starting with 1 and ending with 0, over ∑ = {0, 1}.

R = 1 (0+1)* 0

Write the regular expression for the language starting and ending with a and having any combination of b's in between.

R = a b* a

Write the regular expression for the language starting with a but not having consecutive b’s.

R = {a + ab}*

Amity School of Engineering & Technology

17 of 18

More Examples

Write the regular expression for the language accepting all the string in which any number of a's is followed by any number of b's is followed by any number of c’s.

R = a* b* c*

Write the regular expression for the language over ∑ = {0} having even length of the string.

R = (00)*

Write the regular expression for the language L over ∑ = {0, 1} such that all the string do not contain the substring 01.

R = (1* 0*)

Amity School of Engineering & Technology

18 of 18

More Examples

Write the regular expression for the language containing the string in which every 0 is immediately followed by 11.

R = (011 + 1)*

Describe the language denoted by following regular expression
r.e. = (b* (aaa)* b*)*
The language can be predicted from the regular expression by finding the meaning of it. We will first split the regular expression as:
r.e. = (any combination of b's) (aaa)* (any combination of b's)
L = {The language consists of the string in which a's appear triples, there is no restriction on the number of b's}

Amity School of Engineering & Technology