S. J. P. N.

TRUST’S
HIRASUGAR INSTITUTE OF TECHNOLOGY, NIDASOSHI
Accredited at 'A' Grade by NAAC
Programmes Accredited by NBA: CSE, ECE, EEE & ME.
Department of Computer Science & Engineering
Course: Theory of Computation(BCS503)
Module 2: Regular Expressions and
Languages

Prof. A. A. Daptardar
Asst. Prof. , Dept. of Computer Science & Engg.,
Hirasugar Institute of Technology, Nidasoshi
Regular Expressions

2
REGULAR EXPRESSIONS

What is a RE?

3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 FINITE AUTOMATA &
REGULAR EXPRESSIONS
RE  E NFA
DFA  RE

23
Relation between DFA, NFA,
ENFA & RE

24
OBTAIN ENFA FROM RE

RE  E NFA

25
26
27
28
29
30
31
32
33
34
35
36
37
OBTAIN RE FROM FA

DFA  RE (Kleene’s Theorem)

38
 Identity Rules for Regular
Expressions
• Two Regular Expressions p and q are
equivalent if p and q represent the same
set of strings.
• We now give the identities for regular
expressions, these are useful for
simplifying the regular expressions.

39
40
Kleene’s Theorem

41
42
43
44
45
46
47
48
Another Approach is:

49
50
51
OBTAIN RE FROM FA

DFA  RE (By Eliminating States)

52
53
54
55
56
57
58
59
 Applications of RE
• Regular Expressions in UNIX
– Eg. grep (Global search for RE and Print)
• Pattern Matching
• Lexical Analysis
– First phase of CD

60
Properties of Regular
Languages

61
4.1 Proving Languages not to be Regular
4.2 Closure Properties of Regular
Languages
4.4 Equivalence and Minimization of
Automata

62
 4.2 Closure Properties of
Regular Languages
• In this section, we shall prove several theorems of the
form “if certain languages are regular, and a language L
is formed from them by certain operations (e.g., L is the
union of two regular languages), then L is also regular”.
• These theorems are often called closure properties of
the regular languages, since they show that the class of
regular languages is dosed under the operation
mentioned.
• Closure properties express the idea that when one (or
several) languages are regular, then certain related
languages arc also regular.

63
• Here is a summary of the principal closure
properties for regular languages:
1. The union of two regular languages is regular.
2. The intersection of two regular languages is regular·.
3. The complement of a regular language is regular.
4. The difference of two regular languages is regular.
5. The reversal of a regular language is regular.
6. The closure (star) of a regular language is regular.
7. The concatenation of regular languages is regular.
8. A homomorphism (substitution of strings for symbols) of
a regular language is regular.
9. The inverse homomorphism of a regular language is
regular.
64
• 4.2.1 Closure of Regular Languages
Under Boolean Operations
• Our first closure properties are the three
boolean operations: union, intersection,
and complementation:

65
• Closure Under Complementation
• Starting with a regular expression, we could find
a regular expression for its complement as
follows:
1. Convert the regular expression to an e-NFA.
2. Convert that ENFA to a DFA by the subset construction.
3. Complement the accepting states of that DFA.
4. Turn the complement DFA back into a regular expression using
the construction 66
67
68
69
70
71
72
REGULAR EXPRESSIONS

73
74
75
76
77
78
79
 4.4 Equivalence and
Minimization of Automata
• In this section we discuss how to test whether two
descriptors for regular languages are equivalent, in the
sense that they define the same language.
• An important consequence of this test is that there is a
way to minimize a DFA. That is, we can take any DFA
and find an equivalent DFA that has the minimum
number of states.
• In fact, this DFA is essentially unique: given any two
minimum-state DFA 's that are equivalent, we can
always find a way to rename the states so that the two
DFA's become the same.

80
 4.4.1 Testing Equivalence of
States
• The language generated by a DFA is unique. But, there
can exist ·many DFA' s that accept the same language.
• In such cases, the DFA's are said to be equivalent.
• During computations, it is desirable to represent the DFA
with fewer states since the space is proportional to the
number of states of DFA.
• For storage efficiency, it is required to reduce the
number of states and there by minimize the DFA.
• This can be achieved first by finding the distinguishable
and indistinguishable states.

81
82
83
84
85
• Minimize the following DFA.

86
 4.1 Proving Languages not to
be Regular
• Not every language is a regular language.
In this section, we shall introduce a
powerful technique, known as the
"pumping lemma," for showing certain
languages not to be regular.
– 4.1.1 The Pumping Lemma for Regular
Languages
– 4.1.2 Applications of the Pumping Lemma

87
4.1.1 The Pumping Lemma for Regular
Languages

88
89
90
 4.1.2 Applications of Pumping
Lemma
• The general strategy used to prove that
certain language is not regular is shown
below:
– Assume that the language L is regular and the
number of states in FA be n.
– Select the string say w and break it into the substrings
x, y and z such that w = xyz with the constraints |w| ≥
n, |xy| ≤ n and |y| ≥ 1.
– Find any i such that xyiz Ɇ L. According to pumping
lemma, xyiz ϵ L. So, the result is contradiction to the
assumption that the language is regular. Therefore,
91
the given language L is not regular.
• Example: Show that L = {wwR | w ϵ (0+1)*} is not regular.
• Step1: Let L is regular and n be the number of states in
FA. Consider the string

92
93
 and so number of a’s followed by equal
number of b’s does not exist. But,
according to pumping lemma, n number of
a’s should be followed by n number of b’s
which is a contradiction to the assumption
that the language is regular.
• So, the language L = {anbn | n ≥ 0} is not
regular.

94
95