1

00:00:05,810 --> 00:00:11,039

Okay, so we have strings.

The empty string and string "abc".

2

00:00:11,039 --> 00:00:13,200

And we can take the head

3

00:00:13,200 --> 00:00:15,615

of a string and the

tail of the string,

4

00:00:15,615 --> 00:00:18,480

since we regard them as

lists of characters.

5

00:00:18,480 --> 00:00:22,230

We also introduced the

notion of a language.

6

00:00:22,230 --> 00:00:25,305

A language is just

a set of strings.

7

00:00:25,305 --> 00:00:26,700

So here's a language.

8

00:00:26,700 --> 00:00:28,275

It contains the empty string,

9

00:00:28,275 --> 00:00:30,360

the string hello, string foobar,

10

00:00:30,360 --> 00:00:31,965

the string, which is

11

00:00:31,965 --> 00:00:34,874

just a character a and

the string abc.

12

00:00:34,874 --> 00:00:37,800

There will be also other

languages, which for example,

13

00:00:37,800 --> 00:00:39,780

contain infinitely many strings.

14

00:00:39,780 --> 00:00:42,190

Actually that will

happen quite often.

15

00:00:42,190 --> 00:00:45,560

Now, you've seen this operation

16

00:00:45,560 --> 00:00:47,660

of concatenation of two strings.

17

00:00:47,660 --> 00:00:50,840

So if you have the string

foo and a string bar,

18

00:00:50,840 --> 00:00:53,255

we can just put them

next to each other.

19

00:00:53,255 --> 00:00:57,725

We will now extend that

notion also told languages.

20

00:00:57,725 --> 00:01:02,270

So assume you have a

language A and a language B.

21

00:01:02,270 --> 00:01:05,825

That means we take every

string from the language

22

00:01:05,825 --> 00:01:11,195

A and concatenate it with every

string of the language B.

23

00:01:11,195 --> 00:01:13,160

Here's an example.

24

00:01:13,160 --> 00:01:14,750

If you have the language A

25

00:01:14,750 --> 00:01:17,030

containing foo and bar as strings,

26

00:01:17,030 --> 00:01:20,585

and the language B containing

a and b as strings.

27

00:01:20,585 --> 00:01:23,000

Then concatenating

these two languages

28

00:01:23,000 --> 00:01:27,110

means I take foo with this a and b,

29

00:01:27,110 --> 00:01:28,625

giving fooa and foob,

30

00:01:28,625 --> 00:01:30,905

and I take bar and

concatenated with

31

00:01:30,905 --> 00:01:34,160

a and b, giving bara and barb.

32

00:01:34,160 --> 00:01:36,185

So the pointer is we're

33

00:01:36,185 --> 00:01:39,110

overloading this notion

of concatenating

34

00:01:39,110 --> 00:01:45,020

two strings also to

concatenating two languages.

35

00:01:45,020 --> 00:01:48,890

Okay, here are two corner

cases of this definition.

36

00:01:48,890 --> 00:01:51,395

What happens if I

have any language,

37

00:01:51,395 --> 00:01:54,470

say A, and I concatenate it with

38

00:01:54,470 --> 00:01:58,640

the language which contains

only the empty string.

39

00:01:58,640 --> 00:02:02,270

And secondly, if I

have any language,

40

00:02:02,270 --> 00:02:04,220

say again A, and I

41

00:02:04,220 --> 00:02:05,870

concatenate it with the language

42

00:02:05,870 --> 00:02:08,345

which doesn't contain any string.

43

00:02:08,345 --> 00:02:11,720

How would these two

cases be defined?

44

00:02:11,720 --> 00:02:16,055

Remember, this language here

contains a single element,

45

00:02:16,055 --> 00:02:17,645

namely the empty string,

46

00:02:17,645 --> 00:02:20,210

while this language 

47

00:02:20,210 --> 00:02:23,585

does not contain any

string. It is empty.

48

00:02:23,585 --> 00:02:26,930

So these are two

different languages.

49

00:02:26,930 --> 00:02:29,960

Think about how this

would be defined.

50

00:02:29,960 --> 00:02:33,455

So what's the point of

all these definitions?

51

00:02:33,455 --> 00:02:36,110

Well, we want to make precise

52

00:02:36,110 --> 00:02:38,735

what is the meaning of

a regular expression.

53

00:02:38,735 --> 00:02:41,510

For this, we use

this function L. It

54

00:02:41,510 --> 00:02:44,180

will take a regular expression as

55

00:02:44,180 --> 00:02:47,150

argument and generates a

56

00:02:47,150 --> 00:02:49,970

set of strings or a language.

57

00:02:49,970 --> 00:02:52,670

And it's supposed to be the

language which contains

58

00:02:52,670 --> 00:02:56,330

all the strings this regular

expression can match.

59

00:02:56,330 --> 00:02:58,670

So remember the 0

regular expression,

60

00:02:58,670 --> 00:03:01,115

it's not supposed to

match any string.

61

00:03:01,115 --> 00:03:05,105

So we give it the empty

language or empty set.

62

00:03:05,105 --> 00:03:06,740

This regular expression,

63

00:03:06,740 --> 00:03:09,380

the one regular expression

is supposed to match

64

00:03:09,380 --> 00:03:13,445

exactly one string,

namely the empty string.

65

00:03:13,445 --> 00:03:15,710

the regular expression

66

00:03:15,710 --> 00:03:18,875

recognizing just the

character c, in this case.

67

00:03:18,875 --> 00:03:22,820

Well, that will be the

language which contains

68

00:03:22,820 --> 00:03:28,175

the string only containing

the single character c. 

69

00:03:28,175 --> 00:03:31,295

Now, what is this regular

expression supposed to match?

70

00:03:31,295 --> 00:03:34,835

Well, a string is matched

by this regular expression

71

00:03:34,835 --> 00:03:37,355

if it is matched by

the first component, r1,

72

00:03:37,355 --> 00:03:40,970

or by the second component, r2.

73

00:03:40,970 --> 00:03:43,190

That's why this plus

is the alternative.

74

00:03:43,190 --> 00:03:45,605

So which are the strings

75

00:03:45,605 --> 00:03:48,320

this regular expression

can match? Well,

76

00:03:48,320 --> 00:03:51,275

all the strings

r1 one can match,

77

00:03:51,275 --> 00:03:54,170

given by L(r1) union...

78

00:03:54,170 --> 00:03:57,380

all the strings

R2 can match.

79

00:03:57,380 --> 00:04:01,325

And we use here the union

because this alternative,

80

00:04:01,325 --> 00:04:05,945

even if it says this string

is matched by r1 or by r2.

81

00:04:05,945 --> 00:04:08,465

The meaning of this

reg expression

82

00:04:08,465 --> 00:04:11,209

is the union of both languages.

83

00:04:11,209 --> 00:04:14,315

Now the sequence case.

84

00:04:14,315 --> 00:04:17,960

This means a string is

matched by this regular expression

85

00:04:17,960 --> 00:04:20,510

if the first part of this

string is matched by r1

86

00:04:20,510 --> 00:04:24,935

and the second part of

the string is matched by r2.

87

00:04:24,935 --> 00:04:28,490

Now we have to say, which

are all the strings

88

00:04:28,490 --> 00:04:31,645

this regular expression

can match. Well, it's

89

00:04:31,645 --> 00:04:34,495

all the strings

r1 can match,

90

00:04:34,495 --> 00:04:39,205

concatenated with all the

strings r2 can match.

91

00:04:39,205 --> 00:04:42,895

So for this, we have to use

this concatenation operation.

92

00:04:42,895 --> 00:04:47,440

So if r1 can match a string

and r2 can match a string,

93

00:04:47,440 --> 00:04:51,220

then in the meaning will be

the concatenation of that.

94

00:04:51,220 --> 00:04:53,170

So with this function L

95

00:04:53,170 --> 00:04:56,995

we can make precise

what are the strings,

96

00:04:56,995 --> 00:05:00,205

*all* the strings a regular

expression can match.

97

00:05:00,205 --> 00:05:04,689

The only case we haven't

specified yet is the r*.

98

00:05:04,689 --> 00:05:07,750

For this, we need

another operation

99

00:05:07,750 --> 00:05:12,470

on languages or sets of

strings, which we do next.

100

00:05:12,490 --> 00:05:17,285

We introduce a power

operation for languages.

101

00:05:17,285 --> 00:05:19,100

The power operation or

102

00:05:19,100 --> 00:05:22,835

the nth power is

defined recursively.

103

00:05:22,835 --> 00:05:26,615

So the A to the power of 0

104

00:05:26,615 --> 00:05:31,205

would be defined as the set

containing the empty string.

105

00:05:31,205 --> 00:05:36,200

And A to the power of

n + 1 would be A

106

00:05:36,200 --> 00:05:38,705

concatenated with

A to the power of

107

00:05:38,705 --> 00:05:42,160

n. Here are a few examples.

108

00:05:42,160 --> 00:05:45,380

A to the power of four

would be essentially

109

00:05:45,380 --> 00:05:47,660

A concatenated with

A concatenated with

110

00:05:47,660 --> 00:05:49,640

A concatenated with A,

111

00:05:49,640 --> 00:05:51,650

and also concatenated with

112

00:05:51,650 --> 00:05:55,580

the language which

contains the empty string.

113

00:05:55,580 --> 00:05:57,275

Because that's how we define

114

00:05:57,275 --> 00:05:59,975

the base case, A