1

00:00:05,880 --> 00:00:09,700

Welcome back.

Remember this slide.

2

00:00:09,700 --> 00:00:11,500

This slide said what is

3

00:00:11,500 --> 00:00:14,500

our regular expression matcher

actually supposed to do?

4

00:00:14,500 --> 00:00:16,570

It will take two arguments,

5

00:00:16,570 --> 00:00:18,670

a regular expression r and a string s.

6

00:00:18,670 --> 00:00:21,580

And it's supposed to say yes,

7

00:00:21,580 --> 00:00:23,440

the regular expression matches

8

00:00:23,440 --> 00:00:26,920

the string if and only

if the string is in

9

00:00:26,920 --> 00:00:28,855

the language of r.

10

00:00:28,855 --> 00:00:32,410

And if the string is not

in the language of r,

11

00:00:32,410 --> 00:00:35,515

then our algorithm has to say no.

12

00:00:35,515 --> 00:00:37,210

And we can't use

13

00:00:37,210 --> 00:00:39,565

this specification

directly because remember,

14

00:00:39,565 --> 00:00:43,305

this L sometimes

produces infinite sets.

15

00:00:43,305 --> 00:00:47,585

And we can't test whether a

string is in infinite set,

16

00:00:47,585 --> 00:00:50,090

at least not easily.

17

00:00:50,090 --> 00:00:52,340

And so what we have to do

18

00:00:52,340 --> 00:00:54,260

instead is we have

to be a bit more

19

00:00:54,260 --> 00:00:57,050

clever and implement

some operations

20

00:00:57,050 --> 00:00:59,284

on regular expressions instead,

21

00:00:59,284 --> 00:01:03,275

because regular expressions

are always finite trees.

22

00:01:03,275 --> 00:01:05,870

I should say the

person who has been

23

00:01:05,870 --> 00:01:08,150

clever is called Brzozowski.

24

00:01:08,150 --> 00:01:11,435

It's his algorithm

I'm introducing here.

25

00:01:11,435 --> 00:01:15,515

And his algorithm consists

of two functions.

26

00:01:15,515 --> 00:01:17,840

One is called

nullable and it takes

27

00:01:17,840 --> 00:01:20,104

a regular expression as argument.

28

00:01:20,104 --> 00:01:24,155

And the idea is that

this function nullable is

29

00:01:24,155 --> 00:01:26,450

testing whether

the regular expression

30

00:01:26,450 --> 00:01:27,950

can match the empty string.

31

00:01:27,950 --> 00:01:30,305

So 0 cannot match any string.

32

00:01:30,305 --> 00:01:33,275

So it cannot match the

empty string either.

33

00:01:33,275 --> 00:01:35,465

So that's defined as false.

34

00:01:35,465 --> 00:01:37,775

This regular expression,

the whole purpose

35

00:01:37,775 --> 00:01:39,680

is that it can match

the empty string.

36

00:01:39,680 --> 00:01:41,645

So it's defined as true.

37

00:01:41,645 --> 00:01:44,599

If a regular expression

can match a character,

38

00:01:44,599 --> 00:01:47,045

then it cannot match

the empty string.

39

00:01:47,045 --> 00:01:49,445

So that is defined as false.

40

00:01:49,445 --> 00:01:53,180

If an alternative can

match the empty string,

41

00:01:53,180 --> 00:01:56,960

then either r1 can

match the empty string,

42

00:01:56,960 --> 00:01:59,720

or r2 can match the empty string.

43

00:01:59,720 --> 00:02:03,110

So either nullable

of r1 has to hold,

44

00:02:03,110 --> 00:02:06,945

or nullable of r2 has to hold.

45

00:02:06,945 --> 00:02:09,925

In this sequence, it's

the other way around.

46

00:02:09,925 --> 00:02:12,790

If this regular expression can

match the empty string,

47

00:02:12,790 --> 00:02:16,615

then r1 has to be able to

match the empty string,

48

00:02:16,615 --> 00:02:20,290

and r2 has to be able to

match the empty string.

49

00:02:20,290 --> 00:02:22,555

So here it's just the opposite.

50

00:02:22,555 --> 00:02:25,660

In one case it is or and

the other case it is and.

51

00:02:25,660 --> 00:02:27,970

The star regular

expression can match

52

00:02:27,970 --> 00:02:30,445

always the empty string.

So that is true.

53

00:02:30,445 --> 00:02:33,340

So this is a simple

recursive function

54

00:02:33,340 --> 00:02:37,179

and it should not be too

difficult to implement.

55

00:02:37,179 --> 00:02:42,025

Okay, this nullable function

that is easy-peasy.

56

00:02:42,025 --> 00:02:44,604

The second function, however,

57

00:02:44,604 --> 00:02:49,155

is a bit more involved and

that's just to be expected.

58

00:02:49,155 --> 00:02:53,075

Remember people working in

this area already for decades.

59

00:02:53,075 --> 00:02:57,305

If they have some problems

with runtime, for example,

60

00:02:57,305 --> 00:02:58,940

we can't expect that 

61

00:02:58,940 --> 00:03:03,260

a simple fix will solve all

the problems in the world.

62

00:03:03,260 --> 00:03:06,530

So I admit the second

function is a bit more

63

00:03:06,530 --> 00:03:10,085

complicated and make sure

that you understand it.

64

00:03:10,085 --> 00:03:12,140

And it also just

shows this Brzozowski

65

00:03:12,140 --> 00:03:14,345

is a very clever guy.

66

00:03:14,345 --> 00:03:15,800

Actually, I have to say he was

67

00:03:15,800 --> 00:03:17,720

a clever guy because

I think he either

68

00:03:17,720 --> 00:03:21,650

died last year or

the year before.

69

00:03:21,650 --> 00:03:25,505

And he came up with this

algorithm already in 1964.

70

00:03:25,505 --> 00:03:27,260

It somehow got lost,

71

00:03:27,260 --> 00:03:30,305

but has been rediscovered

in the last ten years.

72

00:03:30,305 --> 00:03:34,685

So the idea of the second

function is the following.

73

00:03:34,685 --> 00:03:38,120

Imagine you have a

regular expression and it can

74

00:03:38,120 --> 00:03:41,930

match a string of the

form c followed by s.

75

00:03:41,930 --> 00:03:44,810

So the c is the first

character of that string.

76

00:03:44,810 --> 00:03:48,605

So I imagine that r can

match this kind of string.

77

00:03:48,605 --> 00:03:50,330

The question is now,

78

00:03:50,330 --> 00:03:52,400

what would a regular

expression look

79

00:03:52,400 --> 00:03:54,695

like that can match just

80

00:03:54,695 --> 00:03:57,140

s. You probably remember

81

00:03:57,140 --> 00:03:59,300

that from the semantic

derivative,

82

00:03:59,300 --> 00:04:00,860

there was also

something of chopping

83

00:04:00,860 --> 00:04:02,210

off the first character.

84

00:04:02,210 --> 00:04:04,940

Here it's the same.

If a regular expression

85

00:04:04,940 --> 00:04:07,835

can match a string

starting with a c,

86

00:04:07,835 --> 00:04:11,090

we're looking for a regular

expression which can match

87

00:04:11,090 --> 00:04:15,215

the rest of the string where

the c has been chopped off.

88

00:04:15,215 --> 00:04:17,690

And this operation will be called

89

00:04:17,690 --> 00:04:21,049

the derivative of a

regular expression.

90

00:04:21,049 --> 00:04:22,205

And it will also take

91

00:04:22,205 --> 00:04:25,460

a character as argument

and a regular expression.

92

00:04:25,460 --> 00:04:28,730

And in contrast to

the semantic 

93

00:04:28,730 --> 00:04:31,310

derivative, which works

94

00:04:31,310 --> 00:04:34,430

over languages or

sets of strings,

95

00:04:34,430 --> 00:04:39,620

this derivative works

over regular expressions.

96

00:04:39,620 --> 00:04:41,330

Okay, here's this function.

97

00:04:41,330 --> 00:04:43,970

It's defined recursively over

98

00:04:43,970 --> 00:04:46,370

the structure of regular expressions.

99

00:04:46,370 --> 00:04:48,814

The first argument

is the character,

100

00:04:48,814 --> 00:04:52,700

and the second one is

a regular expression.

101

00:04:52,700 --> 00:04:56,510

And remember the idea

is we're looking for

102

00:04:56,510 --> 00:05:00,680

a regular expression that

can match everything

103

00:05:00,680 --> 00:05:03,125

this regular expression

as argument can match

104

00:05:03,125 --> 00:05:07,040

except for the c. So now let's

look at this first case.

105

00:05:07,040 --> 00:05:10,550

So this reg expression

cannot match any string.

106

00:05:10,550 --> 00:05:14,270

So it certainly cannot

match any string starting

107

00:05:14,270 --> 00:05:16,910

a c. So we have to look

108

00:05:16,910 --> 00:05:20,090

for a regular expression which

can not match anything.

109

00:05:20,090 --> 00:05:22,700

Well, that's the purpose

of this regular expression,

110

00:05:22,700 --> 00:05:24,815

so we define it as 0.

111

00:05:24,815 --> 00:05:28,130

In the next case,

this regular expression