SSK5204 Chapter 4:
Properties of Regular Languages
Dr. Nor Fazlida Mohd Sani, Dept. of Computer Science,
Fac. of Computer Science and Information Technology, UPM.
Closure properties
Example
The language L of strings that end in 101 is regular
(0+1)*101
How about the language L of strings that do not end
in 101?
Example
Hint: w does not end in 101 if and only if it ends in:
000, 001, 010, 011, 100, 110 or 111
or it has length 0, 1, or 2
So L can be described by the regular expression
(0+1)*(000+001+010+010+100+110+111)
+ e + (0 + 1) + (0 + 1)(0 + 1)
Complement
The complement L of a language L is the set of all
strings that are not in L
Examples (S = {0, 1})
L1 = all strings that end in 101
L1 = all strings that do not end in 101
= all strings end in 000, , 111 or have length 0, 1, or 2
L2 = 1* = {e, 1, 11, 111, }
L2 = all strings that contain at least one 0
= (0 + 1)*0(0 + 1)*
Example
The language L of strings that contain 101 is regular
(0+1)*101(0+1)*
How about the language L of strings that do not
contain 101?
You can write a regular expression,
but it is a lot of work!
Closure under complement
If L is a regular language, so is L.
To argue this, we can use any of the equivalent
definitions for regular languages:
regular
expression
NFA
DFA
The DFA definition will be most convenient
We assume L has a DFA, and show L also has a DFA
Arguing closure under complement
Suppose L is regular, then it has a DFA M
accepts L
Now consider the DFA M with the accepting and
rejecting states of M reversed
accepts strings not in L
this is exactly L
Food for thought
Can we do the same thing with an NFA?
NO!
0, 1
q0
q1
q2
(0+1)*10
q1
q2
(0+1)*
0, 1
q0
Intersection
The intersection L L is the set of strings that are in
both L and L
Examples:
L = (0 + 1)*11
L = 1*
L L = 1*11
L = (0 + 1)*10
L = 1*
L L =
If L, L are regular, is L L also regular?
10
Closure under intersection
If L and L are regular languages, so is L
L.
To argue this, we can use any of the equivalent
definitions for regular languages:
regular
expression
NFA
DFA
Suppose L and L have DFAs, call them M and M
Goal: Construct a DFA (or NFA) for L L
11
An example
1
M
r0
1
0
r1
s0
L = even number of 0s
r0, s0
1
1
s1
L = odd number of 1s
1
1
r1, s0
r0, s1
0
1
1
r1, s1
L L = even number of 0s and odd number of 1s
12
Closure under intersection
states
M and M
DFA for L L
Q = {r1, ..., rn}
Q = {s1, ..., sn}
Q Q = {(r1, s1), (r1, s2), ...,
(r2, s1), ..., (rn, sn)}
start state ri for M
sj for M
(ri, sj)
accepting F for M
F for M
states
F F = {(ri, sj): ri F, sj F}
Whenever M is in state ri and M is in state sj,
the DFA for L L will be in state (ri, sj)
13
Closure under intersection
DFA for L L
M and M
transitions
ri
si
14
a
a
rj
in M
sj
in M
ri, si
rj, sj
Reversal
The reversal wR of a string w is w written backwards
w = cave
wR = evac
The reversal LR of a language L is the language
obtained by reversing all its strings
L = {cat, dog}
15
LR = {tac, god}
Reversal of regular languages
L = all strings that end in 101 is regular
(0+1)*101
How about LR?
This is the language of all strings beginning in 101
Yes, because it is represented by
101(0+1)*
16
Closure under reversal
If L is a regular language, so is LR.
How do we argue?
regular
expression
17
NFA
DFA
Arguing closure under reversal
Take a regular expression E for L
We will show how to reverse E
A regular expression can be of the following types:
18
The special symbols and e
Alphabet symbols like a, b
The union, concatenation, or star of simpler expressions
Proof of closure under reversal
regular expression E
reversal ER
a (alphabet symbol)
E1 + E2
E1R + E2R
E1E2
E2RE1R
E1*
(E1R)*
19
A question
LDUP = {ww: w L}
Ex. L = {cat, dog}
LDUP = {catcat, dogdog}
If L is regular, is LDUP also regular?
regular
expression
20
NFA
DFA
A question
Lets try with regular expression:
LDUP
L = {a, b}
= LL
LDUP = {aa, bb}
LL = {aa, ab, ba, bb}
Lets try with NFA:
q0
21
NFA for L
NFA for L
q1
An example
L = 0*1 is regular
LDUP = {1, 01, 001, 0001, ...}
LDUP = {11, 0101, 001001, 00010001, ...}
= {0n10n1: n 0}
Lets try to design an NFA for LDUP
22
An example
0
01
001
0001
LDUP = {11, 0101, 001001, 00010001, ...}
= {0n10n1: n 0}
23
Non-regular languages
24
A non-regular language
An example
L = {0n1n: n 0} is not regular.
We reason by contradiction:
25
Suppose we have managed to construct a DFA M for L
We argue something must be wrong with this DFA
In particular, M must accept some strings outside L
A non-regular language
imaginary DFA for L with n states
What happens when we run M on input x = 0n+11n+1?
26
M better accept, because x L
A non-regular language
0
M
0
0r1n+1
What happens when we run M on input x = 0n+11n+1?
27
M better accept, because x L
But since M has n states, it must revisit at least one of its
states while reading 0n+1
Pigeonhole principle
Suppose you are tossing n + 1 balls into n
bins. Then two balls end up in the same bin.
Here, balls are 0s, bins are states:
If you have a DFA with n states and it reads
n + 1 consecutive 0s, then it must end up in
the same state twice.
28
A non-regular language
0
M
0
0r1n+1
What happens when we run M on input x = 0n+11n+1?
29
M better accept, because x L2
But since M has n states, it must revisit at least one of its
states while reading 0n+1
But then the DFA must contain a loop with 0s
A non-regular language
0
M
0
0r1n+1
The DFA will then also accept strings that go around
the loop multiple times
But such strings have more 0s than 1s, so they are
not in L2!
30
General method for showing non-regularity
Every regular language L has a property:
an
a1
ak
ak+1 an-1
an+1am
For every sufficiently long input z in L, there is a
middle part in z that, even if repeated any number
of times, keeps the input inside L
31
Pumping lemma for regular languages
Pumping lemma: For every regular language L
There exists a number n such that for every
string z in L, we can write z = u v w where
|uv| n
|v| 1
For every i 0, the string u vi w is in L.
32
Arguing non-regularity
If L is regular, then:
There exists n such that for every z in L, we
can write z = u v w where |uv| n, |v| 1
and
For every i 0, the string u vi w is in L.
So to prove L is not regular, it is enough to show:
For every n there exists z in L, such that for
every way of writing z = u v w where
|uv| n and |v| 1, the string u vi w is not
in L for some i 0.
33
Proving non regularity
For every n there exists z in L, such that for
every way of writing z = u v w where
|uv| n and |v| 1, the string u vi w is not
in L for some i 0.
This is a game between you and an imagined
adversary
adversary
1 choose n
2 write z = uvw (|uv| n,|v| 1)
34
you
choose z L
choose i
you win if uviw L
Arguing non-regularity
You need to give a strategy that, regardless of what
the adversary does, always wins you the game
adversary
1 choose n
2 write z = uvw (|uv| n,|v| 1)
35
you
choose z L
choose i
you win if uviw L
Example
adversary
you
1 choose n
2 write z = uvw (|uv| n,|v| 1)
choose z L
choose i
you win if uviw L
L = {0n1n: n 0}
adversary
you
z = 0 n 1n
i=2
1 choose
write z = uvw
2 n
000000000000000111111111111111
0000000000000000000111111111111111
36
uv2w = 0n+k1n L
Example
LDUP = {0n10n1: n 0}
adversary
you
z = 0n10n1
i=2
1 choose
write z = uvw
2 n
uv2w = 0n+k10n1 L
000000000000001000000000000001
0000000000000000001000000000000001
37
Which of these are regular?
L1 = {x: x has same number of 0s and 1s}
L2 = {x: x = 0n1m, n > m 0}
L3 = {x: x has same number of patterns 01 and 10}
L4 = {x: x has same number of patterns 01 and 10}
L5 = {x: x has different number of 0s and 1s}
38
S = {0, 1}
Example
L1 = {x: x has same number of 0s and 1s}
adversary
you
z = 0 n 1n
i=2
1 choose
write z = uvw
2 n
uv2w = 0n+k1n L3
00000000000000011111111111111
v
w
1 u
0000000000000000000111111111111111
39
Example
L2 = {x: x = 0m1n, m > n 0}
adversary
you
z = 0n+11n
i=0
1 choose
write z = uvw
2 n
uv0w
000000000000000111111111111111
00000000000111111111111111
40
= 0j+l1n+1 L2
Example
L3 = {x: x has same number of 01s and 11s}
adversary
you
1 choose
z = (01)n(11)n
nn = 1
z = 0111 L4
has too many 11s
What we have in mind:
n=1
n=2
n=3
41
z = 011
z = 010111
z = 010101111
z = (01)n1n
has n 01s and n 11s
Example
L3 = {x: x has same number of 01s and 11s}
adversary
you win!
z = (01)n1n
i=0
1 choose
write z = uvw
2 n
010101010101010111111111
Taking out v will kill
at least one 01,
but it does not kill any 11s
010101010101010111111111
so uv0w L3
010101010101010111111111
or
or
42
u v
w
w
Example
L4 = {x: x has same number of 01s and 10s}
adversary
you
z = (01)n(10)n
1 choose
43
n=1
n=2
z = 0110
z = 01011010
n=3
z = 010101101010
Example
L4 = {x: x has same number of 01s and 10s}
is regular!
adversary
you
z = (01)n(10)n
i = 20
1 choose
write z = uvw
2 n
010101101010
u v
01010101101010
u v v
44
5 01 patterns
5 10 patterns
6 01 patterns
6 10 patterns
0101101010
4 01 patterns
4 10 patterns
Example
1
1
r0
q0
s0
1
0
one more 10
one more 01
r1
s1
L4 = {x: x has same number of 01s and 10s}
45
Example
L4 = {x: x has different number of 0s than 1s}
adversary
1 choose
you
z=?
there is an easier way!
L1 = {x: x has same number of 0s and 1s} = L4
If L4 is regular, then L1 = L4 is also regular
But L1 is not regular, so L4 cannot be regular
46
DFA minimization
47
Example
Construct a DFA over alphabet {0, 1} that accepts
those strings that end in 111
Isnt there a smaller one?
48
Smaller DFA
0
q0
1
0
q1
q2
Can we do it with 3 states?
49
q3
Even smaller DFA?
Suppose we had a 3 state DFA M for L
lets imagine what happens when:
inputs:
e, 1, 11, 111
By the pigeonhole principle, on two of these inputs M
ends in the same state
50
Pigeonhole principle
Suppose you are tossing n + 1 balls into n
bins, and Then two balls end up in the
same bin.
Here, balls are inputs, bins are states:
If you have a DFA with n states and you run
it on n + 1 inputs, then two of them end up in
same state.
51
A smaller DFA
Suppose M ends up in the same state after reading
inputs x = 1 and y = 11
inputs:
e, 1, 11, 111
11, 111
ends in 111
Then after reading one more 1
The state of x1 = 11 should be rejecting
The state of y1 = 111 should be accepting
but they are both the same state!
52
1, 11
A smaller DFA
Suppose M ends up in the same state after reading
inputs x = e and y = 1
inputs:
e, 1, 11, 111
11, 111
ends in 111
Then after reading 11
The state of x1 = 11 should be rejecting
The state of y1 = 111 should be accepting
but they are both the same state!
53
e, 1
No smaller DFA!
After looking at all possible pairs for x, y, x y
(e, 1)
(e, 11)
(1, 11)
(e, 111)
(1, 111)
we conclude that
There is no DFA with 3 states for L
So, this DFA is minimal
0
q0
1
0
q1
0
0
54
q2
q3
(11, 111)
DFA minimization
We will show how to turn any DFA for L into
the minimal DFA for L
55
Minimal DFAs and distinguishable states
First, we have to understand minimal DFAs:
reject
accept
0
q0
1
0
q1
q2
q3
0
0
minimal DFA
56
every pair of
states is
distinguishable
Distinguishable states
Two states q and q are distinguishable if
q
w1
w2
wk-1
wk
w1
w2
wk-1
wk
on the same continuation string w1w2...wk, one
accepts, but the other rejects
57
Examples of distinguishable states
0
q0
q1
0
(q0, q1)
distinguishable by 01
(q0, q2)
distinguishable by 1
(q0, q3)
distinguishable by e
(q1, q2)
distinguishable by 1
(q1, q3)
distinguishable by e
(q2, q3)
distinguishable by e
58
1
0
q2
q3
DFA is minimal
Examples of distinguishable states
0
q0
q3
(q0, q3)
distinguishable by e
(q1, q3)
distinguishable by e
(q2, q3)
distinguishable by e
(q1, q2)
distinguishable by 0
(q0, q2)
distinguishable by 0
(q0, q1)
indistinguishable
59
0
q01
1
0, 1
q2
0, 1
1
1
0, 1
0, 1
q1
q2
q3
indistinguishable
pairs can be merged
Examples of distinguishable states
0
q0
0, 1
q2
q01
1
q1
0, 1
q3
0, 1
(q0, q2)
distinguishable by e
(q1, q2)
distinguishable by e
(q0, q3)
distinguishable by e
(q1, q3)
distinguishable by e
(q0, q1)
indistinguishable
(q2, q3)
indistinguishable
60
0, 1
0, 1
q23
Finding (in)distinguishable states
Rule 1:
Rule 2:
q1
q1
a
q2
Rule 3:
61
q2
If q is accepting and q is
rejecting
Mark (q, q) as distinguishable
(x)
If (q1, q1) are marked,
Mark (q2, q2) as distinguishable
(x)
Unmarked pairs are
indistinguishable
Merge them into groups
Example of DFA minimization
0
0
0
q0
qe
1
0
q1
q0
q00
q01
1
q10
0
0
0
q11
q00
q01
q10
q11
62
q1
qe q0 q1 q00 q01 q10
Example of DFA minimization
0
0
0
q0
qe
1
0
q1
q0
q00
q01
1
q10
q1
1
0
0
0
q11
q00
q01
q10
q11
x x x x x x
qe q0 q1 q00 q01 q10
q11 is distinguishable from all other states
63
Example of DFA minimization
0
0
0
q0
qe
1
0
q1
q0
q00
q01
1
q10
q1
1
0
0
0
q11
q00
q01
q10
q11
0 1
x x x x x x
qe q0 q1 q00 q01 q10
Look at pair qe, q0
Neither (q0, q00) nor (q1, q01) are distinguishable
64
Example of DFA minimization
0
0
0
q0
qe
1
0
q1
q0
q00
q01
1
q10
q1
1
0
0
0
q11
Look at pair qe, q1
(q1, q11) is distinguishable
65
q00
q01
0 1
q10
q11
x x x x x x
qe q0 q1 q00 q01 q10
Example of DFA minimization
0
0
0
q0
qe
1
0
q1
q0
q00
q01
1
q10
q1
1
0
0
0
q11
q00
q01
x x
q10
x
x
x x x x x x
q11
1
x x
x
qe q0 q1 q00 q01 q10
After going thru the whole table once
Now we make another pass
66
Example of DFA minimization
0
0
0
q0
qe
1
0
q1
q0
q00
q01
1
q10
q1
1
0
0
0
q11
q00
q01
q10
q11
x x0 1
x
x x
x
x
x
x x x x x x
qe q0 q1 q00 q01 q10
Look at pair qe, q0
Neither (q1, q00) nor (q1, q01) are distinguishable
67
Example of DFA minimization
0
0
0
q0
qe
1
0
q1
q0
q00
q01
1
q10
q1
1
0
0
0
q11
q00
1 x
q01
x x
q10
x
x
x x x x x x
q11
1
x x
x
qe q0 q1 q00 q01 q10
Look at pair qe, q00
Neither (q0, q00) nor (q1, q01) are distinguishable
68
Example of DFA minimization
0
0
0
q0
qe
1
0
q1
q0
q00
q01
1
q10
q1
1
0
0
0
q11
q00
q01
x x
q10
x
x
x x x x x x
q11
1
x x
x
qe q0 q1 q00 q01 q10
In the second pass, nothing changes
So we are ready to apply Rule 3
69
Example of DFA minimization
q00
q0
q01
qe
q10
q1
q11
q0
q1
x x
q00
q01
x x
q10
x
x
x x x x x x
q11
qe q0 q1 q00 q01 q10
Merge unmarked pairs into groups
70
Example of DFA minimization
q00
q0
q01
qe
q10
q1
q11
B
C
q0
q1
q00
q01
q10
q11
A
x
A
x
A
x
x
A
x
A
x
x
B x
x A x
x x x x
qe q0 q1 q00 q01 q10
Merge unmarked pairs into groups
71
Example of DFA minimization
0
0
0
q0
qe
1
0
q1
q0
q00
q01
1
q10
q1
1
0
q01
q00
q10
q11
q11
A
x
A
x
A
x
x
A
x
A
x
x
B x
x A x
x x x x
qe q0 q1 q00 q01 q10
minimized DFA:
qA
1
0
qB
0
72
qC
Example of DFA minimization
0
qA
1
0
qB
qC
How do we know this DFA is minimal?
qB
Answer: All pairs are distinguishable
qC
1
e e
qA qB
73
