1 1

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

     3 Okay, so we have strings.

     4 The empty string and string "abc".

     5 

     6 2

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

     8 And we can take the head

     9 

    10 3

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

    12 of a string and the

    13 tail of the string,

    14 

    15 4

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

    17 since we regard them as

    18 lists of characters.

    19 

    20 5

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

    22 We also introduced the

    23 notion of a language.

    24 

    25 6

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

    27 A language is just

    28 a set of strings.

    29 

    30 7

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

    32 So here's a language.

    33 

    34 8

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

    36 It contains the empty string,

    37 

    38 9

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

    40 the string hello, string foobar,

    41 

    42 10

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

    44 the string, which is

    45 

    46 11

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

    48 just a character a and

    49 the string abc.

    50 

    51 12

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

    53 There will be also other

    54 languages, which for example,

    55 

    56 13

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

    58 contain infinitely many strings.

    59 

    60 14

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

    62 Actually that will

    63 happen quite often.

    64 

    65 15

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

    67 Now, you've seen this operation

    68 

    69 16

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

    71 of concatenation of two strings.

    72 

    73 17

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

    75 So if you have the string

    76 foo and a string bar,

    77 

    78 18

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

    80 we can just put them

    81 next to each other.

    82 

    83 19

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

    85 We will now extend that

    86 notion also told languages.

    87 

    88 20

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

    90 So assume you have a

    91 language A and a language B.

    92 

    93 21

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

    95 That means we take every

    96 string from the language

    97 

    98 22

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

   100 A and concatenate it with every

   101 string of the language B.

   102 

   103 23

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

   105 Here's an example.

   106 

   107 24

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

   109 If you have the language A

   110 

   111 25

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

   113 containing foo and bar as strings,

   114 

   115 26

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

   117 and the language B containing

   118 a and b as strings.

   119 

   120 27

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

   122 Then concatenating

   123 these two languages

   124 

   125 28

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

   127 means I take foo with this a and b,

   128 

   129 29

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

   131 giving fooa and foob,

   132 

   133 30

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

   135 and I take bar and

   136 concatenated with

   137 

   138 31

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

   140 a and b, giving bara and barb.

   141 

   142 32

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

   144 So the pointer is we're

   145 

   146 33

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

   148 overloading this notion

   149 of concatenating

   150 

   151 34

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

   153 two strings also to

   154 concatenating two languages.

   155 

   156 35

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

   158 Okay, here are two corner

   159 cases of this definition.

   160 

   161 36

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

   163 What happens if I

   164 have any language,

   165 

   166 37

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

   168 say A, and I concatenate it with

   169 

   170 38

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

   172 the language which contains

   173 only the empty string.

   174 

   175 39

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

   177 And secondly, if I

   178 have any language,

   179 

   180 40

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

   182 say again A, and I

   183 

   184 41

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

   186 concatenate it with the language

   187 

   188 42

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

   190 which doesn't contain any string.

   191 

   192 43

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

   194 How would these two

   195 cases be defined?

   196 

   197 44

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

   199 Remember, this language here

   200 contains a single element,

   201 

   202 45

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

   204 namely the empty string,

   205 

   206 46

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

   208 while this language 

   209 

   210 47

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

   212 does not contain any

   213 string. It is empty.

   214 

   215 48

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

   217 So these are two

   218 different languages.

   219 

   220 49

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

   222 Think about how this

   223 would be defined.

   224 

   225 50

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

   227 So what's the point of

   228 all these definitions?

   229 

   230 51

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

   232 Well, we want to make precise

   233 

   234 52

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

   236 what is the meaning of

   237 a regular expression.

   238 

   239 53

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

   241 For this, we use

   242 this function L. It

   243 

   244 54

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

   246 will take a regular expression as

   247 

   248 55

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

   250 argument and generates a

   251 

   252 56

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

   254 set of strings or a language.

   255 

   256 57

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

   258 And it's supposed to be the

   259 language which contains

   260 

   261 58

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

   263 all the strings this regular

   264 expression can match.

   265 

   266 59

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

   268 So remember the 0

   269 regular expression,

   270 

   271 60

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

   273 it's not supposed to

   274 match any string.

   275 

   276 61

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

   278 So we give it the empty

   279 language or empty set.

   280 

   281 62

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

   283 This regular expression,

   284 

   285 63

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

   287 the one regular expression

   288 is supposed to match

   289 

   290 64

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

   292 exactly one string,

   293 namely the empty string.

   294 

   295 65

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

   297 the regular expression

   298 

   299 66

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

   301 recognizing just the

   302 character c, in this case.

   303 

   304 67

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

   306 Well, that will be the

   307 language which contains

   308 

   309 68

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

   311 the string only containing

   312 the single character c. 

   313 

   314 69

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

   316 Now, what is this regular

   317 expression supposed to match?

   318 

   319 70

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

   321 Well, a string is matched

   322 by this regular expression

   323 

   324 71

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

   326 if it is matched by

   327 the first component, r1,

   328 

   329 72

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

   331 or by the second component, r2.

   332 

   333 73

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

   335 That's why this plus

   336 is the alternative.

   337 

   338 74

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

   340 So which are the strings

   341 

   342 75

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

   344 this regular expression

   345 can match? Well,

   346 

   347 76

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

   349 all the strings

   350 r1 one can match,

   351 

   352 77

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

   354 given by L(r1) union...

   355 

   356 78

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

   358 all the strings

   359 R2 can match.

   360 

   361 79

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

   363 And we use here the union

   364 because this alternative,

   365 

   366 80

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

   368 even if it says this string

   369 is matched by r1 or by r2.

   370 

   371 81

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

   373 The meaning of this

   374 reg expression

   375 

   376 82

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

   378 is the union of both languages.

   379 

   380 83

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

   382 Now the sequence case.

   383 

   384 84

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

   386 This means a string is

   387 matched by this regular expression

   388 

   389 85

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

   391 if the first part of this

   392 string is matched by r1

   393 

   394 86

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

   396 and the second part of

   397 the string is matched by r2.

   398 

   399 87

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

   401 Now we have to say, which

   402 are all the strings

   403 

   404 88

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

   406 this regular expression

   407 can match. Well, it's

   408 

   409 89

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

   411 all the strings

   412 r1 can match,

   413 

   414 90

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

   416 concatenated with all the

   417 strings r2 can match.

   418 

   419 91

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

   421 So for this, we have to use

   422 this concatenation operation.

   423 

   424 92

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

   426 So if r1 can match a string

   427 and r2 can match a string,

   428 

   429 93

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

   431 then in the meaning will be

   432 the concatenation of that.

   433 

   434 94

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

   436 So with this function L

   437 

   438 95

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

   440 we can make precise

   441 what are the strings,

   442 

   443 96

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

   445 *all* the strings a regular

   446 expression can match.

   447 

   448 97

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

   450 The only case we haven't

   451 specified yet is the r*.

   452 

   453 98

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

   455 For this, we need

   456 another operation

   457 

   458 99

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

   460 on languages or sets of

   461 strings, which we do next.

   462 

   463 100

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

   465 We introduce a power

   466 operation for languages.

   467 

   468 101

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

   470 The power operation or

   471 

   472 102

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

   474 the nth power is

   475 defined recursively.

   476 

   477 103

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

   479 So the A to the power of 0

   480 

   481 104

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

   483 would be defined as the set

   484 containing the empty string.

   485 

   486 105

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

   488 And A to the power of

   489 n + 1 would be A

   490 

   491 106

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

   493 concatenated with

   494 A to the power of

   495 

   496 107

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

   498 n. Here are a few examples.

   499 

   500 108

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

   502 A to the power of four

   503 would be essentially

   504 

   505 109

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

   507 A concatenated with

   508 A concatenated with

   509 

   510 110

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

   512 A concatenated with A,

   513 

   514 111

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

   516 and also concatenated with

   517 

   518 112

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

   520 the language which

   521 contains the empty string.

   522 

   523 113

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

   525 Because that's how we define

   526 

   527 114

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

   529 the base case, A

   530 to the power of 0.

   531 

   532 115

   533 00:05:59,975 --> 00:06:03,410

   534 And A to the power

   535 one would be just A,

   536 

   537 116

   538 00:06:03,410 --> 00:06:05,330

   539 again followed by that one,

   540 

   541 117

   542 00:06:05,330 --> 00:06:07,790

   543 but this would be just A.

   544 

   545 118

   546 00:06:07,790 --> 00:06:10,385

   547 And A to the power 0

   548 

   549 119

   550 00:06:10,385 --> 00:06:14,270

   551 is this language which

   552 contains the empty string.

   553 

   554 120

   555 00:06:14,270 --> 00:06:16,670

   556 With this power operation,

   557 

   558 121

   559 00:06:16,670 --> 00:06:19,505

   560 I can also fill in this case.

   561 

   562 122

   563 00:06:19,505 --> 00:06:23,210

   564 Remember this r* operation

   565 is supposed to match

   566 

   567 123

   568 00:06:23,210 --> 00:06:27,680

   569 a string with either

   570 0 or more copies of r.

   571 

   572 124

   573 00:06:27,680 --> 00:06:31,940

   574 So the meaning of this

   575 regular expression would be

   576 

   577 125

   578 00:06:31,940 --> 00:06:37,475

   579 now the Union of all the

   580 powers greater or equal than 0,

   581 

   582 126

   583 00:06:37,475 --> 00:06:40,835

   584 of the language that r can match.

   585 

   586 127

   587 00:06:40,835 --> 00:06:44,945

   588 And we take now at the

   589 union of all these powers,

   590 

   591 128

   592 00:06:44,945 --> 00:06:47,150

   593 that means essentially what

   594 

   595 129

   596 00:06:47,150 --> 00:06:48,530

   597 can the regular expression match

   598 

   599 130

   600 00:06:48,530 --> 00:06:51,440

   601 if I take L of r

   602 to the 0th power,

   603 

   604 131

   605 00:06:51,440 --> 00:06:53,030

   606 what can I match with

   607 

   608 132

   609 00:06:53,030 --> 00:06:57,305

   610 the first power, the

   611 second power, and so on.

   612 

   613 133

   614 00:06:57,305 --> 00:07:00,544

   615 And I take the union

   616 of all these powers.

   617 

   618 134

   619 00:07:00,544 --> 00:07:03,830

   620 That's the definition

   621 of which strings

   622 

   623 135

   624 00:07:03,830 --> 00:07:05,510

   625 this regular expression

   626 is supposed to

   627 

   628 136

   629 00:07:05,510 --> 00:07:08,510

   630 match. The meaning of

   631 this regular expression.

   632 

   633 137

   634 00:07:08,510 --> 00:07:11,300

   635 This is such an

   636 important definition,

   637 

   638 138

   639 00:07:11,300 --> 00:07:13,250

   640 that there's actually

   641 a name for it.

   642 

   643 139

   644 00:07:13,250 --> 00:07:15,020

   645 It's called the Kleene star.

   646 

   647 140

   648 00:07:15,020 --> 00:07:16,400

   649 And it's written like this.

   650 

   651 141

   652 00:07:16,400 --> 00:07:18,335

   653 If I have a language A,

   654 

   655 142

   656 00:07:18,335 --> 00:07:21,785

   657 I can build the star

   658 of this language

   659 

   660 143

   661 00:07:21,785 --> 00:07:26,255

   662 by union up all the powers

   663 greater or equal than 0.

   664 

   665 144

   666 00:07:26,255 --> 00:07:28,580

   667 The A-star of

   668 

   669 145

   670 00:07:28,580 --> 00:07:31,580

   671 a language would expand

   672 to a to the power 0,

   673 

   674 146

   675 00:07:31,580 --> 00:07:33,770

   676 union A to the power of one,

   677 

   678 147

   679 00:07:33,770 --> 00:07:36,665

   680 A to the power of two, and so on.

   681 

   682 148

   683 00:07:36,665 --> 00:07:39,230

   684 And it would

   685 essentially mean, well,

   686 

   687 149

   688 00:07:39,230 --> 00:07:43,460

   689 it's the language which contains

   690 the empty string because

   691 

   692 150

   693 00:07:43,460 --> 00:07:48,290

   694 of the A to the 0, one copy of A,

   695 

   696 151

   697 00:07:48,290 --> 00:07:51,020

   698 two concatenated copies of A,

   699 

   700 152

   701 00:07:51,020 --> 00:07:55,070

   702 three concatenated

   703 copies of A, and so on.

   704 

   705 153

   706 00:07:55,070 --> 00:07:59,060

   707 So that's what this A-star

   708 is defined as.

   709 

   710 154

   711 00:07:59,060 --> 00:08:03,725

   712 Essentially as the Union

   713 of all the powers.

   714 

   715 155

   716 00:08:03,725 --> 00:08:05,990

   717 And it's essentially

   718 each power is how many

   719 

   720 156

   721 00:08:05,990 --> 00:08:08,750

   722 times I have to

   723 concatenate this language A.

   724 

   725 157

   726 00:08:08,750 --> 00:08:13,549

   727 And note that this language

   728 A-star will always contain

   729 

   730 158

   731 00:08:13,549 --> 00:08:21,240

   732 the empty string because that

   733 is how the A^0 is defined.

   734 

   735 159

   736 00:08:21,310 --> 00:08:23,540

   737 So in this definition,

   738 

   739 160

   740 00:08:23,540 --> 00:08:25,969

   741 I could have also written star

   742 

   743 161

   744 00:08:25,969 --> 00:08:29,180

   745 here because the

   746 meaning of this r*,

   747 

   748 162

   749 00:08:29,180 --> 00:08:34,055

   750 regular expression

   751 is the Kleene star of

   752 

   753 163

   754 00:08:34,055 --> 00:08:37,130

   755 the language of r.

   756 Remember that's

   757 

   758 164

   759 00:08:37,130 --> 00:08:41,525

   760 the union of all powers

   761 greater or equal than 0.

   762 

   763 165

   764 00:08:41,525 --> 00:08:43,640

   765 It's behind.

   766 I hope you don't get

   767 

   768 166

   769 00:08:43,640 --> 00:08:45,800

   770 confused by the use of the stars.

   771 

   772 167

   773 00:08:45,800 --> 00:08:48,845

   774 This star is for

   775 the regular expressions.

   776 

   777 168

   778 00:08:48,845 --> 00:08:52,205

   779 That star is for languages.

   780 

   781 169

   782 00:08:52,205 --> 00:08:54,274

   783 They are two

   784 different operations.

   785 

   786 170

   787 00:08:54,274 --> 00:08:56,555

   788 They don't even

   789 have the same type.

   790 

   791 171

   792 00:08:56,555 --> 00:08:58,954

   793 Here might be

   794 something interesting.

   795 

   796 172

   797 00:08:58,954 --> 00:09:00,560

   798 Remember I asked you to think

   799 

   800 173

   801 00:09:00,560 --> 00:09:03,035

   802 about these two corner cases.

   803 

   804 174

   805 00:09:03,035 --> 00:09:04,730

   806 I hope you have done so,

   807 

   808 175

   809 00:09:04,730 --> 00:09:07,070

   810 but let's also have look

   811 at this together.

   812 

   813 176

   814 00:09:07,070 --> 00:09:09,785

   815 According to the definition

   816 

   817 177

   818 00:09:09,785 --> 00:09:11,930

   819 for this append of languages,

   820 

   821 178

   822 00:09:11,930 --> 00:09:13,670

   823 I have to take every string in

   824 

   825 179

   826 00:09:13,670 --> 00:09:16,130

   827 this set and have

   828 

   829 180

   830 00:09:16,130 --> 00:09:18,695

   831 two concatenated with

   832 every string in that set.

   833 

   834 181

   835 00:09:18,695 --> 00:09:22,115

   836 So this set contains only

   837 the empty string as element.

   838 

   839 182

   840 00:09:22,115 --> 00:09:24,820

   841 So if I concatenate anything in

   842 

   843 183

   844 00:09:24,820 --> 00:09:27,745

   845 there with the empty string,

   846 that will be left untouched.

   847 

   848 184

   849 00:09:27,745 --> 00:09:31,855

   850 So this one will be

   851 actually A.

   852 

   853 185

   854 00:09:31,855 --> 00:09:34,600

   855 This one I have to

   856 take every string in

   857 

   858 186

   859 00:09:34,600 --> 00:09:36,190

   860 this language and I have to

   861 

   862 187

   863 00:09:36,190 --> 00:09:39,115

   864 concatenate with every

   865 string in that language.

   866 

   867 188

   868 00:09:39,115 --> 00:09:41,110

   869 But here isn't any string.

   870 

   871 189

   872 00:09:41,110 --> 00:09:43,300

   873 So I can't concatenate that.

   874 

   875 190

   876 00:09:43,300 --> 00:09:46,900

   877 That will be actually

   878 the empty set (not empty string).

   879 

   880 191

   881 00:09:46,900 --> 00:09:49,570

   882 So now let's have

   883 

   884 192

   885 00:09:49,570 --> 00:09:51,670

   886 a look at regular expressions.

   887 

   888 193

   889 00:09:51,670 --> 00:09:53,230

   890 That was with languages.

   891 

   892 194

   893 00:09:53,230 --> 00:09:56,035

   894 But let's have a look at

   895 regular expressions now.

   896 

   897 195

   898 00:09:56,035 --> 00:09:58,660

   899 What would be the

   900 meaning, for example,

   901 

   902 196

   903 00:09:58,660 --> 00:10:01,945

   904 of r followed by 1?

   905 

   906 197

   907 00:10:01,945 --> 00:10:04,149

   908 That is a regular expression.

   909 

   910 198

   911 00:10:04,149 --> 00:10:06,255

   912 And it essentially says:

   913 

   914 199

   915 00:10:06,255 --> 00:10:07,850

   916 this regular expression matches

   917 

   918 200

   919 00:10:07,850 --> 00:10:10,685

   920 some strings and this matches

   921 the empty string.

   922 

   923 201

   924 00:10:10,685 --> 00:10:13,730

   925 So if you find out

   926 what the meaning is,

   927 

   928 202

   929 00:10:13,730 --> 00:10:16,955

   930 we would apply this

   931 L-function to it.

   932 

   933 203

   934 00:10:16,955 --> 00:10:19,430

   935 And if we now look

   936 up the definition,

   937 

   938 204

   939 00:10:19,430 --> 00:10:27,360

   940 that would be L of r

   941 appended L of 1.

   942 

   943 205

   944 00:10:27,850 --> 00:10:32,255

   945 If you look up what

   946 this is defined,

   947 

   948 206

   949 00:10:32,255 --> 00:10:41,640

   950 then this would be L of r

   951 appended with this language.

   952 

   953 207

   954 00:10:41,950 --> 00:10:46,325

   955 And if you now look up

   956 our definition earlier,

   957 

   958 208

   959 00:10:46,325 --> 00:10:50,455

   960 that will be just L of r.

   961 

   962 209

   963 00:10:50,455 --> 00:10:52,690

   964 What that essentially

   965 

   966 210

   967 00:10:52,690 --> 00:10:55,765

   968 means is if you have

   969 this regular expression,

   970 

   971 211

   972 00:10:55,765 --> 00:10:58,885

   973 this will match

   974 exactly those strings

   975 

   976 212

   977 00:10:58,885 --> 00:11:01,000

   978 which this regular

   979 expression can match.

   980 

   981 213

   982 00:11:01,000 --> 00:11:04,794

   983 And that pretty much

   984 coincides with our intuition.

   985 

   986 214

   987 00:11:04,794 --> 00:11:05,950

   988 This is supposed to match

   989 

   990 215

   991 00:11:05,950 --> 00:11:08,410

   992 the empty string at

   993 the end of the string,

   994 

   995 216

   996 00:11:08,410 --> 00:11:11,005

   997 so it doesn't really

   998 make any difference.

   999 

  1000 217

  1001 00:11:11,005 --> 00:11:13,480

  1002 And the meaning

  1003 really tells us that.

  1004 

  1005 218

  1006 00:11:13,480 --> 00:11:15,880

  1007 But here's the

  1008 interesting thing.

  1009 

  1010 219

  1011 00:11:15,880 --> 00:11:17,979

  1012 When you were in school,

  1013 

  1014 220

  1015 00:11:17,979 --> 00:11:23,124

  1016 how would you think

  1017 about this expression?

  1018 

  1019 221

  1020 00:11:23,124 --> 00:11:29,515

  1021 Well, r times 1

  1022 equals just our, okay?

  1023 

  1024 222

  1025 00:11:29,515 --> 00:11:33,634

  1026 Furthermore, if you had r times 0.

  1027 

  1028 223

  1029 00:11:33,634 --> 00:11:35,045

  1030 What would that be equal?

  1031 

  1032 224

  1033 00:11:35,045 --> 00:11:37,205

  1034 Well, it would be 0.

  1035 

  1036 225

  1037 00:11:37,205 --> 00:11:39,650

  1038 Ok, let's have

  1039 

  1040 226

  1041 00:11:39,650 --> 00:11:42,605

  1042 a look how that works out

  1043 with regular expressions.

  1044 

  1045 227

  1046 00:11:42,605 --> 00:11:46,355

  1047 So if you take r followed by 0,

  1048 

  1049 228

  1050 00:11:46,355 --> 00:11:48,260

  1051 remember this is

  1052 the regular expression

  1053 

  1054 229

  1055 00:11:48,260 --> 00:11:49,895

  1056 that cannot match anything.

  1057 

  1058 230

  1059 00:11:49,895 --> 00:11:52,415

  1060 By unfolding the definition,

  1061 

  1062 231

  1063 00:11:52,415 --> 00:11:59,104

  1064 I would get L of r

  1065 appended with L of 0.

  1066 

  1067 232

  1068 00:11:59,104 --> 00:12:01,775

  1069 This is of course defined as L of r

  1070 

  1071 233

  1072 00:12:01,775 --> 00:12:05,915

  1073 appended with the empty set.

  1074 

  1075 234

  1076 00:12:05,915 --> 00:12:10,760

  1077 And this would, according

  1078 to the definition earlier,

  1079 

  1080 235

  1081 00:12:10,760 --> 00:12:13,830

  1082 well just the empty set.

  1083 

  1084 236

  1085 00:12:14,160 --> 00:12:20,260

  1086 And this would be

  1087 of course L of 0.

  1088 

  1089 237

  1090 00:12:20,260 --> 00:12:24,580

  1091 So it seems like these laws,

  1092 

  1093 238

  1094 00:12:24,580 --> 00:12:27,175

  1095 at least for the times,

  1096 

  1097 239

  1098 00:12:27,175 --> 00:12:29,785

  1099 seem to be valid from math,

  1100 

  1101 240

  1102 00:12:29,785 --> 00:12:31,420

  1103 are also valid with regular expressions,

  1104 

  1105 241

  1106 00:12:31,420 --> 00:12:33,370

  1107 if we look at their meaning.

  1108 

  1109 242

  1110 00:12:33,370 --> 00:12:36,670

  1111 These laws on natural numbers

  1112 

  1113 243

  1114 00:12:36,670 --> 00:12:40,105

  1115 and regular expressions and

  1116 their close correspondance

  1117 

  1118 244

  1119 00:12:40,105 --> 00:12:42,460

  1120 probably explain why I use 

  1121 

  1122 245

  1123 00:12:42,460 --> 00:12:46,975

  1124 a times for the sequence

  1125 regular expression.

  1126 

  1127 246

  1128 00:12:46,975 --> 00:12:51,040

  1129 So r followed by the

  1130 regular expression 1,

  1131 

  1132 247

  1133 00:12:51,040 --> 00:12:54,505

  1134 will have the same meaning

  1135 as that regular expression.