1
00:00:01,160 --> 00:00:05,380
In this video, we're gonna talk about
regular languages which are used to
2
00:00:05,380 --> 00:00:13,999
specify the lexical structure of
programming languages. To briefly review
3
00:00:13,999 --> 00:00:18,849
the lexical structure of a programming
language is a set of token classes. And
4
00:00:18,849 --> 00:00:24,010
each one of the token classes consists of
some set of strings. Now we need a way to
5
00:00:24,010 --> 00:00:28,922
specify which set of strings belongs to
each token class and the usual tool or
6
00:00:28,922 --> 00:00:34,146
doing that is to use regular languages. So
in this video we're going to present like
7
00:00:34,146 --> 00:00:39,431
regular languages and define what they are
and then in subsequent videos we're going
8
00:00:39,431 --> 00:00:45,096
to look at some examples using them in
actual programming languages. To define
9
00:00:45,096 --> 00:00:52,727
the regular languages, we generally use
something called regular expressions. And
10
00:00:52,727 --> 00:00:58,258
each regular expression team now it's a
set. There are two basic regular
11
00:00:58,258 --> 00:01:04,096
expressions. If I write the single
character C, that's an expression and what
12
00:01:04,096 --> 00:01:10,970
at the notes is a language containing one
string. Which is the single character C,
13
00:01:10,970 --> 00:01:17,367
okay, That's one basic form so for any
single character I get a language with a
14
00:01:17,367 --> 00:01:23,925
one string language with just and then the
only string is that character. Another
15
00:01:23,925 --> 00:01:30,807
basic building block of regular languages
is the regular expression epsilon which is
16
00:01:30,807 --> 00:01:36,190
the language. That contains again just a
single string, this time the empty string.
17
00:01:36,190 --> 00:01:41,477
And, one thing that's important to keep in
mind is that epsilon is not the empty
18
00:01:41,477 --> 00:01:46,635
language, okay? So this is not correspond
to the empty string and the empty set of
19
00:01:46,635 --> 00:01:51,540
strings. It is a language that has a
single string namely the empty string.
20
00:01:52,660 --> 00:01:58,046
Besides the two base regular expressions,
there are three compound regular
21
00:01:58,046 --> 00:02:03,942
expressions and we'll just go through them
here in order. The first is a + b which
22
00:02:03,942 --> 00:02:09,911
corresponds to the union of the languages
a and b. So this would be the set a such
23
00:02:09,911 --> 00:02:15,589
that a is in the language of big A, little
a is in the language of big A union,
24
00:02:15,589 --> 00:02:21,849
little b such that b is in the language of
little b so just the union of the two sets
25
00:02:21,849 --> 00:02:27,718
of strings. Concatenation is like string
concatenation. So if I have two languages,
26
00:02:27,718 --> 00:02:33,510
a and b, or two regula r expressions, a
and b, then, the concatenation of a and b
27
00:02:33,510 --> 00:02:40,019
Is equal to all of the strings. Little a
concatenate with little b where a is drawn
28
00:02:40,019 --> 00:02:46,309
from the language big A and little b is
drawn from the language big B. And so this
29
00:02:46,309 --> 00:02:51,105
is cross sporadic operation. Choose a
string from a. Choose a string from
30
00:02:51,105 --> 00:02:56,301
capital B and then combine, put them
together with the string from a first and
31
00:02:56,301 --> 00:03:01,897
choosing strings at all possible ways from
all possible combined strings and that's
32
00:03:01,897 --> 00:03:06,760
the language a concatenated with b. And
finally there's a kind of looping
33
00:03:06,760 --> 00:03:13,206
[inaudible]. This is pronounced a star or
is called the Kleene iteration and, or the
34
00:03:13,206 --> 00:03:21,189
Kleene closure. And a star is equal to the
union. For i greater than = zero of a to
35
00:03:21,189 --> 00:03:28,467
the i, a to the i-th power. What's that
mean? Well, a to the i-th power is just a
36
00:03:28,467 --> 00:03:34,539
to concatenated with itself By times. So
this is, [inaudible]. And note that
37
00:03:34,539 --> 00:03:40,180
because i can be = zero, one of the
possibilities here is a to the zero, so a
38
00:03:40,180 --> 00:03:45,972
concatenate with itself zero times and
what is that, well that's the language
39
00:03:45,972 --> 00:03:51,914
epsilon. So that's the language contain
the empty string. So the empty string is
40
00:03:51,914 --> 00:04:01,072
always an element of a star. To summarize
the last couple of slides the regular
41
00:04:01,072 --> 00:04:06,410
expressions over some alphabet sigma. The
smallest of that expressions that include
42
00:04:06,410 --> 00:04:11,876
the following. So, let's define it so, the
regular expression r are equal to epsilon
43
00:04:11,876 --> 00:04:16,269
is always a regular expression. Or,
another possibility is the single
44
00:04:16,269 --> 00:04:21,650
character c where c is an element of our
alphabet, okay? So this is important the
45
00:04:21,650 --> 00:04:27,161
regular expressions define with respect to
some alphabet. So we have to pick a family
46
00:04:27,161 --> 00:04:32,283
of characters that will form the base
cases of the regular expression and here,
47
00:04:32,283 --> 00:04:37,081
you know? We have one base regular
expression for each character in the
48
00:04:37,081 --> 00:04:42,062
alphabet. And then we have the compound
expressions. So, another possibility Is
49
00:04:42,062 --> 00:04:47,163
that a regular expression is the union of
two regular expressions. Another one is
50
00:04:47,163 --> 00:04:52,199
that the concatenation of two regular
expressions. And the last one is that it
51
00:04:52,199 --> 00:04:58,056
could be the iteration of a regular expre
ssion. So these five cases are the set of
52
00:04:58,056 --> 00:05:03,913
regular expressions over a given alphabet.
Now this syntax here for describing the
53
00:05:03,913 --> 00:05:09,484
regular expressions with these vertical
bars and these different cases on the
54
00:05:09,484 --> 00:05:14,841
right hand side in this recursive
definition of r, If you haven't seen this
55
00:05:14,841 --> 00:05:19,744
before, this is called the grammar. And
that's not important for this lecture.
56
00:05:19,744 --> 00:05:24,576
It's not what this, this lecture is about
but we're talking about grammars when we
57
00:05:24,576 --> 00:05:31,746
get to parsing. Next I'd like to do a few
examples of actually building regular
58
00:05:31,746 --> 00:05:36,020
languages, writing the mountain and
thinking about what they mean. And as we
59
00:05:36,020 --> 00:05:40,236
said, whenever we're talking about a
regular language, we first have to say
60
00:05:40,236 --> 00:05:44,966
what the alphabet is. And so, for these
examples let's just use the alphabet zero
61
00:05:44,966 --> 00:05:49,410
and one. So these are going to be
languages which consists of strings of 0s
62
00:05:49,410 --> 00:05:54,026
and 1s. And let's start with a very simple
example. Let's think about the language
63
00:05:54,197 --> 00:06:01,970
one star And what language that to note.
So, well, we know the definition of star.
64
00:06:01,970 --> 00:06:10,475
If you remember, that was the union over i
greater than = zero of one to the i. Okay.
65
00:06:10,475 --> 00:06:17,451
And what is that equal to? Well, that's
just one. Repeated i that's what the
66
00:06:17,451 --> 00:06:23,755
concatenation of one to the i means, okay.
It means one concatenated with itself i
67
00:06:23,755 --> 00:06:29,436
and so this is going to be the empty
string. That's one concatenated with
68
00:06:29,436 --> 00:06:35,740
itself zero followed by one followed by
eleven followed by one concatenated with
69
00:06:35,740 --> 00:06:41,577
itself three followed by one concatenated
with itself four followed by one
70
00:06:41,577 --> 00:06:47,540
concatenated with itself any number of
times. Okay, And this, and so we can see
71
00:06:47,540 --> 00:06:58,069
that this is just equal to all strings Of
1s, All right? Now let's do a second
72
00:06:58,069 --> 00:07:07,893
example let's think about the language
one. Plus zero concatenated with the
73
00:07:07,893 --> 00:07:16,722
language one, okay? And remember how
concatenation works is across products we
74
00:07:16,722 --> 00:07:25,038
take every string in the first expression
and combining with every string in the
75
00:07:25,038 --> 00:07:34,176
second expression. So this is going to be
equal to the strings a b where a is drawn
76
00:07:34,176 --> 00:07:41,035
from one + zero and b is drawn from one.
All right? And, what can that be when
77
00:07:41,035 --> 00:07:46,741
there's two traces for a. A could be one
or zero and b could be one so in fact this
78
00:07:46,741 --> 00:07:52,104
is equal to the set one, one and the
strings one, one, the second [inaudible]
79
00:07:52,104 --> 00:07:58,576
of the strings one, one and one zero. All
right? Let's do another examples, slightly
80
00:07:58,576 --> 00:08:03,783
more complex. Let's build up here to
having two iterations in a union so have
81
00:08:03,783 --> 00:08:09,057
zero + one and think of about what's
that equal to but we've already know what
82
00:08:09,057 --> 00:08:14,129
one is equal to. That's equal to all
strings of ones and so by analogy zero
83
00:08:14,129 --> 00:08:19,809
must be all strings of zeroes then we take
the union of those two things so this is
84
00:08:19,809 --> 00:08:25,421
actually really easy to write out. Let's
write them out in this notation so we have
85
00:08:25,421 --> 00:08:31,042
zero to the i, for i again equal to zero,
okay. That's zero union with. One to the
86
00:08:31,042 --> 00:08:37,920
i or greater than = zero. That's the
strings of all one. So there's a set at
87
00:08:37,920 --> 00:08:45,170
this expression to nodes. And for our last
example, let's think about zero + one.
88
00:08:45,170 --> 00:08:50,086
Now, that iterated. Okay? So, we put the
star around the union of the two
89
00:08:50,086 --> 00:08:55,846
individual character instead of having the
star on each character individually in
90
00:08:55,846 --> 00:09:01,466
taking the union of the two things. So
what is the, what is this expression equal
91
00:09:01,466 --> 00:09:07,568
to? Well, let's work with the definition
of star. So, we know. That this is the
92
00:09:07,568 --> 00:09:15,243
union over i greater than or equal to zero
of zero + one to the i. And what does that
93
00:09:15,243 --> 00:09:22,477
look like, well, that looks like first of
all, there's the empty string, right? And
94
00:09:22,477 --> 00:09:29,962
then another string in this language is,
is. Excuse me, is drawn from zero + one
95
00:09:29,962 --> 00:09:36,543
and so this, I shouldn't say another
string but another set of strings is the
96
00:09:36,543 --> 00:09:42,953
language zero + one. And then zero + one
concatenated with itself, okay? And in
97
00:09:42,953 --> 00:09:53,511
general, is going to be zero + one
concatenated by itself i times. Now what
98
00:09:53,511 --> 00:09:58,468
does that mean? That means that every
position, if we have a string of length i,
99
00:09:58,468 --> 00:10:03,679
at every position we could pick a zero or
a one to plug in and this works for any
100
00:10:03,679 --> 00:10:08,636
length string. This is gonna be true of
strings of every length and so in fact
101
00:10:08,636 --> 00:10:18,830
this language is just going to be all
strings Of 0's and 1's. In fact, what that
102
00:10:18,830 --> 00:10:23,230
means is this, is the cycle effect on our
alphabet. Our alphabet that consists of
103
00:10:23,230 --> 00:10:27,905
zero and one and so this is the set of all
strings that you can form over the entire
104
00:10:27,905 --> 00:10:32,250
alphabet, And that has a special name when
that happens when you have a regular
105
00:10:32,250 --> 00:10:36,815
expression that denotes the set of all
strings you can form out of the alphabet,
106
00:10:36,815 --> 00:10:41,050
we write that as sigma star, okay? So just
meaning that all the strings of the
107
00:10:41,050 --> 00:10:45,723
alphabet integrated as many times as you
like One last point I wanna make on this
108
00:10:45,888 --> 00:10:50,174
before we go on here is that there are
actually lots of ways to write each of
109
00:10:50,174 --> 00:10:54,790
these different languages. There's not a
unique way to write these. So for example,
110
00:10:54,790 --> 00:10:59,187
let's just take this language here. The
second one that we did, and let me switch
111
00:10:59,187 --> 00:11:03,583
colors. Another alternative way to write
this since we know the meaning of it is
112
00:11:03,583 --> 00:11:08,029
these two strings one, one and one zero, I
could have written it as one, one. + one
113
00:11:08,029 --> 00:11:14,020
zero and that would mean exactly the same
thing. We used two expressions denote
114
00:11:14,020 --> 00:11:20,930
exactly the same set similarly with one
star, I could write this as one . + one.
115
00:11:20,930 --> 00:11:25,646
And cuz this wouldn't change anything.
Adding in the single string one wouldn't
116
00:11:25,646 --> 00:11:30,242
change anything since one is already
included in one. This might be kind of a
117
00:11:30,242 --> 00:11:35,018
silly way to write that set but it doesn't
matter it has a meaning and it means
118
00:11:35,018 --> 00:11:39,914
exactly the same things as one. The point
again is that there is more than one way
119
00:11:39,914 --> 00:11:44,451
to write down the same set to write, to
write, you can write multiple regular
120
00:11:44,451 --> 00:11:49,994
expressions that denote the same set.
Well, it come to the end of this video.
121
00:11:49,994 --> 00:11:55,838
And to summarize, we looked at regular
expressions. Which are used to define
122
00:11:55,838 --> 00:12:01,300
regular languages? And the regular
expressions are syntax, that's the.
123
00:12:01,300 --> 00:12:06,295
Expression that we write down and if it
notes a set of strings which is the
124
00:12:06,295 --> 00:12:11,881
regular language and that's the meaning of
the regular expression. And there are five
125
00:12:11,881 --> 00:12:17,008
kinds of regular expressions in the
standard definition. There's an expression
126
00:12:17,008 --> 00:12:22,266
for the empty string and that's denoted by
epsilon and then we have all the one
127
00:12:22,266 --> 00:12:27,853
character strings and then there are three
compound expressions. Ways of building new
128
00:12:27,853 --> 00:12:32,519
regular expressions from other regular
expressions and these are union,
129
00:12:32,519 --> 00:12:34,360
concatenation, and iteration.