1
00:00:00,000 --> 00:00:04,692
Welcome back. In this video, we're going
to take a little digression and talk about

2
00:00:04,692 --> 00:00:09,328
formal languages. A formal language has
played a big role in theoretical computer

3
00:00:09,328 --> 00:00:14,135
science but they're also very important in
compilers because inside of the compiler,

4
00:00:14,135 --> 00:00:18,656
we typically have several different formal
languages that we're manipulating. A

5
00:00:18,656 --> 00:00:23,406
regular expressions are one example of a
formal language but it's actually helpful

6
00:00:23,406 --> 00:00:28,098
I think in understanding regular languages
and all the formal languages we'll see

7
00:00:28,270 --> 00:00:33,876
later on in later videos to talk about
what the formal languages in general, So,

8
00:00:33,876 --> 00:00:39,728
let's begin with the definition. A formal
language has an alphabet, So, some set of

9
00:00:39,728 --> 00:00:45,508
letter sigma. And then a language over
that alphabet is just a set of strings of

10
00:00:45,508 --> 00:00:51,433
the characters drawn from the alphabet. So
in the case or regular languages, we had

11
00:00:51,433 --> 00:00:56,996
certain ways of building up sets of
strings of characters but other kinds of

12
00:00:56,996 --> 00:01:02,776
languages would have different sets of
strings. And in general, a formal language

13
00:01:02,776 --> 00:01:08,536
is just any set of strings over some
alphabet. An example of a language that

14
00:01:08,536 --> 00:01:13,766
you're familiar with is a form from the
alphabet of English characters and it is

15
00:01:13,766 --> 00:01:18,493
just the set of English sentences. Now,
This is not quite a formal language and

16
00:01:18,493 --> 00:01:22,983
that we might disagree in which string of
English characters are in fact valid

17
00:01:22,983 --> 00:01:27,529
English sentences but one could imagine
that we could define some rules that we

18
00:01:27,529 --> 00:01:32,076
would say the certain strings are English
sentences and others aren't. And if we

19
00:01:32,076 --> 00:01:36,679
could come to this on agreement this would
be a fully formal language. Now a much

20
00:01:36,679 --> 00:01:41,055
more rigorous formal language would be
something like the following; we could

21
00:01:41,055 --> 00:01:45,374
pick our alphabet to be the asking
character set and the language to be the

22
00:01:45,374 --> 00:01:50,262
set of all Valid C program. So this is
definitely a very well defined language.

23
00:01:50,262 --> 00:01:54,979
This is exactly the set of inputs that C
compilers will accept. And the, the

24
00:01:54,979 --> 00:01:59,943
important contrast I want to draw here is
that the alphabet is actually interesting.

25
00:02:00,120 --> 00:02:05,025
So, different formal languages, you know?
Have a very, very different alphabets and

26
00:02:05,025 --> 00:02:09,694
we can't really talk a bout what the
formal language is or what sort of strings

27
00:02:09,694 --> 00:02:14,656
we're interested in unless to find that
alphabet. Another important concept for

28
00:02:14,656 --> 00:02:19,686
many formal languages is a meaning
function. Typically we have one of the

29
00:02:19,686 --> 00:02:25,266
strings in our language and let's call
that some expression e and the expression

30
00:02:25,266 --> 00:02:30,296
e by itself is just a piece of syntax.
It's a program in some sense or it

31
00:02:30,296 --> 00:02:35,188
represents something else that we're,
Which is the thing we're actually

32
00:02:35,188 --> 00:02:40,906
interested in. And so we have a Function L
that maps the strings in the language to

33
00:02:40,906 --> 00:02:46,814
their meanings. And so for example in the
case of the regular expressions, this

34
00:02:46,814 --> 00:02:53,340
would be a regular expression. And that
would be map to a set of strings. The

35
00:02:53,340 --> 00:02:58,740
regular language that, that regular
expression to notes and we saw an example

36
00:02:58,740 --> 00:03:04,490
where we wrote out the meeting function
for regular expression last time so let's

37
00:03:04,490 --> 00:03:10,381
use regular expressions as an example and
I'm gonna first write down the meaning of

38
00:03:10,381 --> 00:03:16,202
the regular expressions. The way I wrote
it down in the last video so if you recall

39
00:03:16,202 --> 00:03:21,953
we had a regular expression epsilon and
that denoted a set, Which contain just one

40
00:03:21,953 --> 00:03:27,565
string, namely the empty string. And then
we had a regular expression C for every

41
00:03:27,565 --> 00:03:33,176
character in the alphabet which also do
need a socketing just one string namely

42
00:03:33,176 --> 00:03:38,648
the single character C. And then, we had a
bunch of compound expressions. So for

43
00:03:38,648 --> 00:03:46,381
example, A + B. That was equal to the
union of the sets A and B and we had the

44
00:03:46,381 --> 00:03:53,661
concatenation so I could, I could
[inaudible] A and B and that was equal to

45
00:03:53,661 --> 00:04:01,301
a cross product where I selected a string
from each set in order and concatenated

46
00:04:01,301 --> 00:04:11,211
them together. And finally there was
iteration so I could write a star and that

47
00:04:11,211 --> 00:04:21,860
was the union over I. Greater than zero of
all the sets A to the I, I ends. An

48
00:04:21,860 --> 00:04:27,118
interesting thing about this definition is
you can see that they were mapping, over

49
00:04:27,118 --> 00:04:32,186
we have expressions and let me switch
colors here, over here we have expressions

50
00:04:32,186 --> 00:04:36,771
and over here we have the sets. But
there's something kind of odd about the

51
00:04:36,771 --> 00:04:41,192
way this is written and not quite right
cuz you can see here we clearly, we have

52
00:04:41,192 --> 00:04:45,614
an expression. We have a piece of syntax A
+ B and then somehow on the other side

53
00:04:45,614 --> 00:04:49,648
this, this A, this A and this B have
magically turned into sets that we're

54
00:04:49,648 --> 00:04:54,069
taking the union of and similarly down
here we're choosing an element from this

55
00:04:54,069 --> 00:04:58,325
set but this set is also an expression and
what does that mean? Somehow we're

56
00:04:58,325 --> 00:05:02,927
conflating the sets in the expressions and
this is what. The meaning function is

57
00:05:02,927 --> 00:05:07,450
intended to fix and this what they, or,
or, or intended to make clear. So we, what

58
00:05:07,450 --> 00:05:14,726
we really wanted to say is that there's
some mapping, That the language L epsilon

59
00:05:14,726 --> 00:05:26,433
is the set so the, so L maps from
expressions into sets of strings. Okay,

60
00:05:26,433 --> 00:05:31,840
It's a function that maps one to the other
and it you haven't seen this notation

61
00:05:31,840 --> 00:05:37,180
before, this is a standard notation for
describing functions. It does says that L

62
00:05:37,180 --> 00:05:42,386
is a function from things in the domain,
in this domain to this range, okay. And

63
00:05:42,386 --> 00:05:47,860
similarly the language of this expression
is the set and it becomes really useful

64
00:05:47,860 --> 00:05:53,228
for the compound expressions cuz here we
say the language of this expression. Is

65
00:05:53,228 --> 00:05:59,309
equal to the language of a union with the
language of B and now you can see the

66
00:05:59,309 --> 00:06:04,934
recursion. First we interpret A and B
using L and we take the union of the

67
00:06:04,934 --> 00:06:10,407
result. Okay, so now it's clear what's
asset and what's an expression and

68
00:06:10,407 --> 00:06:15,652
similarly here the language of a
concatenated with B, we are going to

69
00:06:15,652 --> 00:06:21,961
select elements from the language of these
two expressions and then we're going to

70
00:06:21,961 --> 00:06:27,924
form another set from those two sets. And
finally for iteration, The language of a

71
00:06:27,924 --> 00:06:32,819
star is equal to the union over the
meaning of a bunch of expressions, A to

72
00:06:32,819 --> 00:06:38,171
the I is an expression. This is a, a piece
of syntax and we have to convert it to A

73
00:06:38,171 --> 00:06:43,194
set N order to take the union. And so
about this, is. The proper definition of

74
00:06:43,194 --> 00:06:48,887
the meaning of regular expressions where
we've made the meaning function L explicit

75
00:06:48,887 --> 00:06:54,309
and we've shown exactly how recursively we
apply L to decompose the compound

76
00:06:54,309 --> 00:06:59,528
expressions into several expressions that
we compute the meaning of and then

77
00:06:59,528 --> 00:07:07,341
computed the sets from those from those
separate smaller s ets. So, there's other

78
00:07:07,341 --> 00:07:11,890
reasons for using a meeting function. We
just saw one of them which is to make

79
00:07:11,890 --> 00:07:16,830
clear. What is syntax and what is
semantics in our definitions. Some parts

80
00:07:16,830 --> 00:07:22,143
of the definition are expression and some
parts are the, the meanings or the sets

81
00:07:22,143 --> 00:07:27,521
and the using L makes it clear that the
arguments to L are the, the programs or

82
00:07:27,521 --> 00:07:32,218
the expressions and the results Are the,
the sets. The outputs are the sets, But

83
00:07:32,218 --> 00:07:36,850
there are a couple of other reasons for
separating syntax and semantics. One, is

84
00:07:36,850 --> 00:07:41,255
that it allows us to consider notation as
a separate issue. That is if we have

85
00:07:41,255 --> 00:07:45,944
syntax and semantics being different, then
we can vary the syntax while we keep the

86
00:07:45,944 --> 00:07:50,672
semantics the same and we might discover.
That there, that some kinds of syntax are

87
00:07:50,672 --> 00:07:55,319
better than others for the problems that
we're interested in, for the languages

88
00:07:55,319 --> 00:07:59,908
that we're interested in. And another
reason for separating the two is because

89
00:07:59,908 --> 00:08:04,556
of expressions and meanings because syntax
and semantics are not in one to one

90
00:08:04,556 --> 00:08:09,203
correspondents. And I actually illustrated
this with regular expressions in the

91
00:08:09,203 --> 00:08:14,027
previous video but I want to iterate here
that, that there are generally many more

92
00:08:14,027 --> 00:08:18,684
expressions than there are meanings so
that means there maybe multiple way. To

93
00:08:18,684 --> 00:08:25,170
write an expression that means the same
thing. I'd like to take a moment to

94
00:08:25,170 --> 00:08:30,669
illustrate why separating syntax from
semantics is beneficial for a notation.

95
00:08:30,669 --> 00:08:36,667
So, everybody's familiar with the, the r
number system so I can write numbers like

96
00:08:36,667 --> 00:08:43,000
zero, one. 42 and 107 and there are very
nice algorithms for describing how you add

97
00:08:43,000 --> 00:08:49,470
and subtract and multiply such numbers but
there are older systems of notation for

98
00:08:49,470 --> 00:08:55,706
numbers. Things like the Roman numerals. I
could have the number one. I could have

99
00:08:55,706 --> 00:09:02,098
the number four, the number ten and say
the number 40 I think is written like that

100
00:09:02,098 --> 00:09:07,954
and. And an issue with this number system,
first of all, let me stress that these two

101
00:09:08,165 --> 00:09:13,569
have the same meaning. So the, the
meanings of expressions in this language

102
00:09:13,569 --> 00:09:18,384
are. Are the integers and it's exactly the
same in this language. So the idea, the

103
00:09:18,384 --> 00:09:23,158
mean ing of these two systems are just the
numbers but the notation is extremely

104
00:09:23,158 --> 00:09:27,872
different. The number written in Roman
numerals was completely different from a

105
00:09:27,872 --> 00:09:32,943
number written in Arabic numerals. And the
fact is that the Roman numerals are really

106
00:09:32,943 --> 00:09:37,779
painfully to do addition and subtraction
and multiplication and in fact. Back in

107
00:09:37,779 --> 00:09:43,441
ancient times when this was a common
system was not very well known how to do

108
00:09:43,441 --> 00:09:49,238
it and very few people were actually good
at doing arithmetic with, with the system

109
00:09:49,440 --> 00:09:54,832
because of, because the algorithms were
kind of complicated. And, when we moved to

110
00:09:54,832 --> 00:10:00,762
the, the Arabic system, later, That it was
a big improvement because people, it was

111
00:10:00,762 --> 00:10:05,339
easier for people to learn how to do basic
arithmetic with these kinds of numbers.

112
00:10:05,339 --> 00:10:09,972
And the only thing that changed between
one system and the other was the system of

113
00:10:09,972 --> 00:10:14,493
notation. And so, notation is extremely
important because it governs how you think

114
00:10:14,493 --> 00:10:19,125
and it governs the kinds of things you can
say and the sort of procedures that you

115
00:10:19,125 --> 00:10:23,312
will use. So don't underestimate the
importance of notation and this is one

116
00:10:23,312 --> 00:10:27,609
reason for separating syntax from
semantics because we can leave the idea of

117
00:10:27,609 --> 00:10:31,840
what we're trying to do than numbers
alone. And play with, with different ways

118
00:10:31,840 --> 00:10:37,994
of representing them and we might discover
that some ways are better than others. The

119
00:10:37,994 --> 00:10:43,340
third reason I gave for separating syntax
and semantics is that in many interesting

120
00:10:43,340 --> 00:10:48,176
languages, multiple expressions, multiple
pieces of syntax will have the same

121
00:10:48,176 --> 00:10:53,331
semantics. Now going back again to regular
expressions, let's consider the regular

122
00:10:53,331 --> 00:10:58,990
expression zero<i>. Now there are many ways
to write the same language which is the</i>

123
00:10:58,990 --> 00:11:04,429
language of all strings of zeroes so
string of zeroes of any length. So for

124
00:11:04,429 --> 00:11:09,939
example I could also write that as zero +
zero<i>. Another way to write it is as</i>

125
00:11:09,939 --> 00:11:15,611
epsilon + zero, zero and here you can see
that, that this expression is all the

126
00:11:15,611 --> 00:11:21,268
strings of 0s of at least link one and
then we get the empty string for epsilon

127
00:11:21,268 --> 00:11:26,360
so that is = zero and then just, you
know? Any combination of these things

128
00:11:26,360 --> 00:11:32,088
would also amount to an eq uivalent
language for example that one and so on.

129
00:11:32,088 --> 00:11:37,462
So there's actually an unbounded,
unlimited number of way I could write this

130
00:11:37,462 --> 00:11:43,538
language but all of these mean exactly the
same thing and if you think about it. What

131
00:11:43,538 --> 00:11:50,398
this means is that in general, if I draw
the two domains differently, I think about

132
00:11:50,398 --> 00:11:56,923
different expressions over here and
different distinct meanings over here and

133
00:11:56,923 --> 00:12:03,700
the function L that maps between them. The
function L is many to one. So there are.

134
00:12:03,700 --> 00:12:11,851
Yeah. There are points in the space that
where many different expressions or pieces

135
00:12:11,851 --> 00:12:19,320
of syntax map to the same meaning. And
this is just a general characteristic of

136
00:12:19,320 --> 00:12:24,159
Interesting formal languages and this is
actually extremely important in compilers

137
00:12:24,159 --> 00:12:28,881
because this is the basis of optimization.
The fact that there are many different

138
00:12:28,881 --> 00:12:33,312
programs that are actually functionally
equivalent, that's what allows us to

139
00:12:33,312 --> 00:12:37,860
substitute one program that runs faster
than another, that's what allows us to

140
00:12:37,860 --> 00:12:42,349
replace one program with another if it
runs faster and does exactly the same

141
00:12:42,349 --> 00:12:47,246
thing. So we couldn't do optimization and,
you know the reason we can do optimization

142
00:12:47,246 --> 00:12:52,189
as precisely because the meaning function
is many to one. So meaning is many to one

143
00:12:52,189 --> 00:12:57,109
and keep in mind, important point here
it's never one to many. We don't want the

144
00:12:57,109 --> 00:13:01,628
opposite situation. If we have the
opposite situation, Where L could map a

145
00:13:01,628 --> 00:13:06,929
single point to two different meanings.
Well first of all, this would no longer be

146
00:13:06,929 --> 00:13:11,865
a function but, but also it would mean
that the meaning of certain expressions

147
00:13:11,865 --> 00:13:17,227
say in our programming language was not
well defined. That's that when you wrote a

148
00:13:17,227 --> 00:13:22,284
program was actually ambiguous whether it
meant this or it meant that and that's a

149
00:13:22,284 --> 00:13:27,341
situation we don't like. So, we expect
meaning functions to be many to one for

150
00:13:27,341 --> 00:13:32,338
nontrivial languages and we don't want
them ever to be one too many. And that

151
00:13:32,338 --> 00:13:36,855
concludes today's video. Next time, Going
to go back and continue with our

152
00:13:36,855 --> 00:13:38,800
discussion of lexical analysis.