1

00:00:09,990 --> 00:00:13,465

Welcome back to this

week's lecture.

2

00:00:13,465 --> 00:00:16,450

The task this week is to actually

3

00:00:16,450 --> 00:00:20,320

implement a regular

expression matcher.

4

00:00:20,320 --> 00:00:22,510

And we want to be a bit

5

00:00:22,510 --> 00:00:25,315

faster than the regular

expression matcher

6

00:00:25,315 --> 00:00:29,380

in Python, Ruby,

Javascript, and Java.

7

00:00:29,380 --> 00:00:31,960

Remember this regular expression

8

00:00:31,960 --> 00:00:35,785

and strings which are

just a number of a's,

9

00:00:35,785 --> 00:00:39,670

these regular expression matchers

where abysmally slow.

10

00:00:39,670 --> 00:00:43,170

They could only match

approximately 30 a's in

11

00:00:43,170 --> 00:00:45,665

something like half a minute.

12

00:00:45,665 --> 00:00:49,460

What we like to do with

our regular expression matcher.

13

00:00:49,460 --> 00:00:51,890

We will try a few times,

14

00:00:51,890 --> 00:00:55,505

but our second trial will already

be much, much better.

15

00:00:55,505 --> 00:00:58,400

It will probably

match around maybe

16

00:00:58,400 --> 00:01:02,030

thousand a's in something

in half a minute.

17

00:01:02,030 --> 00:01:03,920

But our third version in

18

00:01:03,920 --> 00:01:06,230

comparison will be

blindingly fast.

19

00:01:06,230 --> 00:01:08,180

And we'll be able to match

20

00:01:08,180 --> 00:01:10,145

strings of length 10,000 a's

21

00:01:10,145 --> 00:01:12,230

and will not require

22

00:01:12,230 --> 00:01:14,975

more than five seconds.

So let's go ahead with that.

23

00:01:14,975 --> 00:01:18,095

We will first implement

24

00:01:18,095 --> 00:01:19,880

our regular expression

matcher only

25

00:01:19,880 --> 00:01:22,069

for the basic

regular expressions.

26

00:01:22,069 --> 00:01:25,430

So we will have only six

cases to think about.

27

00:01:25,430 --> 00:01:27,620

This will simplify matters at first.

28

00:01:27,620 --> 00:01:30,350

Later we can

think about how to

29

00:01:30,350 --> 00:01:34,100

extend that to the extended

regular expressions.

30

00:01:34,100 --> 00:01:37,625

Unfortunately, before we can

start our implementation,

31

00:01:37,625 --> 00:01:39,290

we have to discuss

32

00:01:39,290 --> 00:01:42,470

when two regular

expressions are equivalent.

33

00:01:42,470 --> 00:01:46,595

And we use here this notation

of the triple equals.

34

00:01:46,595 --> 00:01:48,215

We say a regular expression

35

00:01:48,215 --> 00:01:50,180

r1 and r2 are

36

00:01:50,180 --> 00:01:56,059

equivalent if and only

if the language of r1 is

37

00:01:56,059 --> 00:01:59,360

equal to the language of r2.

38

00:01:59,360 --> 00:02:02,915

Sounds complicated,

but essentially means

39

00:02:02,915 --> 00:02:04,700

if the two regular expressions can

40

00:02:04,700 --> 00:02:06,950

match exactly the same strings,

41

00:02:06,950 --> 00:02:09,800

then we want to regard

them as equivalent.

42

00:02:09,800 --> 00:02:14,300

This equivalence justifies

why we can be sloppy

43

00:02:14,300 --> 00:02:16,040

with parentheses.

44

00:02:16,040 --> 00:02:23,870

For example, if we have

(r1 + r2) + r3,

45

00:02:23,870 --> 00:02:32,270

then this will be equivalent

to r1 + (r2 + r3).

46

00:02:32,270 --> 00:02:34,910

Remember, regular

expressions are trees,

47

00:02:34,910 --> 00:02:37,940

so these are two different

regular expressions,

48

00:02:37,940 --> 00:02:41,540

but they can match

the same strings.

49

00:02:41,540 --> 00:02:45,695

Because, well, if we take

here the meaning of that,

50

00:02:45,695 --> 00:02:54,350

that would be just L(r1 + r2 + r3),

51

00:02:54,350 --> 00:03:04,100

which is equal to L(r1 + r2) u L(r3).

52

00:03:04,100 --> 00:03:10,595

And that is equal to of 

53

00:03:10,595 --> 00:03:15,710

L(r1) u L(r2) u L(r3).

54

00:03:15,710 --> 00:03:17,930

And if you do the

same calculation

55

00:03:17,930 --> 00:03:19,445

for that regular expression,

56

00:03:19,445 --> 00:03:22,940

you will find out the

two sets are the same.

57

00:03:22,940 --> 00:03:26,195

So both regular expressions

can match the same strings.

58

00:03:26,195 --> 00:03:28,805

So even if they're different

regular expressions,

59

00:03:28,805 --> 00:03:31,220

we can regard them as eqivalent.

60

00:03:31,220 --> 00:03:33,290

And so that's why we can forget

61

00:03:33,290 --> 00:03:35,270

about writing these parentheses.

62

00:03:35,270 --> 00:03:40,205

Let's have a look

at some more examples.

63

00:03:40,205 --> 00:03:41,870

So the first one here,

64

00:03:41,870 --> 00:03:43,205

that is now clear.

65

00:03:43,205 --> 00:03:45,200

We did this calculation already

66

00:03:45,200 --> 00:03:47,480

for arbitrary regular expressions.

67

00:03:47,480 --> 00:03:49,520

Here it is for

concrete ones a, b and c.

68

00:03:49,520 --> 00:03:52,690

Here on the left-hand side,

69

00:03:52,690 --> 00:03:54,895

the regular expression

has the same meaning

70

00:03:54,895 --> 00:03:56,620

as on the right-hand side.

71

00:03:56,620 --> 00:03:58,420

So they are equivalent.

72

00:03:58,420 --> 00:04:01,375

We can ignore the parentheses.

73

00:04:01,375 --> 00:04:03,220

If I have a choice,

74

00:04:03,220 --> 00:04:06,610

but the choice is

the same a or a,

75

00:04:06,610 --> 00:04:09,265

then this is

equivalent to just a.

76

00:04:09,265 --> 00:04:13,075

So the same choice doesn't

introduce anything more.

77

00:04:13,075 --> 00:04:15,370

In the next case, if I have

78

00:04:15,370 --> 00:04:19,450

a regular expression

which can match a or b,

79

00:04:19,450 --> 00:04:23,860

that can match the same

strings as b or a.

80

00:04:23,860 --> 00:04:27,325

So you have a kind of

commutativity for the plus,

81

00:04:27,325 --> 00:04:29,485

which is like on natural numbers.

82

00:04:29,485 --> 00:04:32,880

But you would not have a

communitivity for the sequence:

83

00:04:32,880 --> 00:04:37,070

if you have

first a and then b,

84

00:04:37,070 --> 00:04:40,850

that's not the same as

matching first b and then a.

85

00:04:40,850 --> 00:04:42,800

So for the sequence ...

86

00:04:42,800 --> 00:04:44,615

they are not equivalent.

87

00:04:44,615 --> 00:04:49,475

However, for the sequence I

can, like for the plus, ignore

88

00:04:49,475 --> 00:04:51,245

prarentheses.

89

00:04:51,245 --> 00:04:55,070

If I have the parentheses

and this way,

90

00:04:55,070 --> 00:04:57,785

or I have it in this way.

91

00:04:57,785 --> 00:05:00,605

These are two different

regular expressions,

92

00:05:00,605 --> 00:05:02,120

but they have the same meaning.

93

00:05:02,120 --> 00:05:03,815

So they are equivalent.

94

00:05:03,815 --> 00:05:05,780

And so I can leave out parentheses

95

00:05:05,780 --> 00:05:09,170

for times as well.

96

00:05:09,170 --> 00:05:12,185

The next one is a slightly

more interesting one.

97

00:05:12,185 --> 00:05:15,020

If I have a regular

expression which can match

98

00:05:15,020 --> 00:05:19,655

c first followed by (a + b),

99

00:05:19,655 --> 00:05:25,355

then this is the same as

first c followed by a,

100

00:05:25,355 --> 00:05:28,640

or c followed by b.

101

00:05:28,640 --> 00:05:31,265

So that's the kind of

distributivity law

102

00:05:31,265 --> 00:05:33,545

on regular expressions.

103

00:05:33,545 --> 00:05:36,350

But they're also regular expressions

which are not equivalent.

104

00:05:36,350 --> 00:05:38,990

If I have the regular

expression which can

105

00:05:38,990 --> 00:05:42,800

match the string containing

exactly two a's.

106

00:05:42,800 --> 00:05:44,240

That is not equivalent

107

00:05:44,240 --> 00:05:46,730

to the regular

expression which can just match

108

00:05:46,730 --> 00:05:49,250

a single a. And similarly

109

00:05:49,250 --> 00:05:51,680

in this case, if I can match

110

00:05:51,680 --> 00:05:56,075

a or the string b followed by c,

111

00:05:56,075 --> 00:05:59,825

that is not the same as a or b,

112

00:05:59,825 --> 00:06:02,000

followed by a or c.

113

00:06:02,000 --> 00:06:05,990

I'll let you think about

why is that not equivalent.

114

00:06:05,990 --> 00:06:08,060

Essentially you

have to find out what's

115

00:06:08,060 --> 00:06:10,475

the meaning of both

regular expressions.

116

00:06:10,475 --> 00:06:14,090

And are they the

same sets or not?