In this video, we're gonna talk about
regular languages which are used to
specify the lexical structure of
programming languages. To briefly review
the lexical structure of a programming
language is a set of token classes. And
each one of the token classes consists of
some set of strings. Now we need a way to
specify which set of strings belongs to
each token class and the usual tool or
doing that is to use regular languages. So
in this video we're going to present like
regular languages and define what they are
and then in subsequent videos we're going
to look at some examples using them in
actual programming languages. To define
the regular languages, we generally use
something called regular expressions. And
each regular expression team now it's a
set. There are two basic regular
expressions. If I write the single
character C, that's an expression and what
at the notes is a language containing one
string. Which is the single character C,
okay, That's one basic form so for any
single character I get a language with a
one string language with just and then the
only string is that character. Another
basic building block of regular languages
is the regular expression epsilon which is
the language. That contains again just a
single string, this time the empty string.
And, one thing that's important to keep in
mind is that epsilon is not the empty
language, okay? So this is not correspond
to the empty string and the empty set of
strings. It is a language that has a
single string namely the empty string.
Besides the two base regular expressions,
there are three compound regular
expressions and we'll just go through them
here in order. The first is a + b which
corresponds to the union of the languages
a and b. So this would be the set a such
that a is in the language of big A, little
a is in the language of big A union,
little b such that b is in the language of
little b so just the union of the two sets
of strings. Concatenation is like string
concatenation. So if I have two languages,
a and b, or two regula r expressions, a
and b, then, the concatenation of a and b
Is equal to all of the strings. Little a
concatenate with little b where a is drawn
from the language big A and little b is
drawn from the language big B. And so this
is cross sporadic operation. Choose a
string from a. Choose a string from
capital B and then combine, put them
together with the string from a first and
choosing strings at all possible ways from
all possible combined strings and that's
the language a concatenated with b. And
finally there's a kind of looping
[inaudible]. This is pronounced a star or
is called the Kleene iteration and, or the
Kleene closure. And a star is equal to the
union. For i greater than = zero of a to
the i, a to the i-th power. What's that
mean? Well, a to the i-th power is just a
to concatenated with itself By times. So
this is, [inaudible]. And note that
because i can be = zero, one of the
possibilities here is a to the zero, so a
concatenate with itself zero times and
what is that, well that's the language
epsilon. So that's the language contain
the empty string. So the empty string is
always an element of a star. To summarize
the last couple of slides the regular
expressions over some alphabet sigma. The
smallest of that expressions that include
the following. So, let's define it so, the
regular expression r are equal to epsilon
is always a regular expression. Or,
another possibility is the single
character c where c is an element of our
alphabet, okay? So this is important the
regular expressions define with respect to
some alphabet. So we have to pick a family
of characters that will form the base
cases of the regular expression and here,
you know? We have one base regular
expression for each character in the
alphabet. And then we have the compound
expressions. So, another possibility Is
that a regular expression is the union of
two regular expressions. Another one is
that the concatenation of two regular
expressions. And the last one is that it
could be the iteration of a regular expre
ssion. So these five cases are the set of
regular expressions over a given alphabet.
Now this syntax here for describing the
regular expressions with these vertical
bars and these different cases on the
right hand side in this recursive
definition of r, If you haven't seen this
before, this is called the grammar. And
that's not important for this lecture.
It's not what this, this lecture is about
but we're talking about grammars when we
get to parsing. Next I'd like to do a few
examples of actually building regular
languages, writing the mountain and
thinking about what they mean. And as we
said, whenever we're talking about a
regular language, we first have to say
what the alphabet is. And so, for these
examples let's just use the alphabet zero
and one. So these are going to be
languages which consists of strings of 0s
and 1s. And let's start with a very simple
example. Let's think about the language
one star And what language that to note.
So, well, we know the definition of star.
If you remember, that was the union over i
greater than = zero of one to the i. Okay.
And what is that equal to? Well, that's
just one. Repeated i that's what the
concatenation of one to the i means, okay.
It means one concatenated with itself i
and so this is going to be the empty
string. That's one concatenated with
itself zero followed by one followed by
eleven followed by one concatenated with
itself three followed by one concatenated
with itself four followed by one
concatenated with itself any number of
times. Okay, And this, and so we can see
that this is just equal to all strings Of
1s, All right? Now let's do a second
example let's think about the language
one. Plus zero concatenated with the
language one, okay? And remember how
concatenation works is across products we
take every string in the first expression
and combining with every string in the
second expression. So this is going to be
equal to the strings a b where a is drawn
from one + zero and b is drawn from one.
All right? And, what can that be when
there's two traces for a. A could be one
or zero and b could be one so in fact this
is equal to the set one, one and the
strings one, one, the second [inaudible]
of the strings one, one and one zero. All
right? Let's do another examples, slightly
more complex. Let's build up here to
having two iterations in a union so have
zero + one and think of about what's
that equal to but we've already know what
one is equal to. That's equal to all
strings of ones and so by analogy zero
must be all strings of zeroes then we take
the union of those two things so this is
actually really easy to write out. Let's
write them out in this notation so we have
zero to the i, for i again equal to zero,
okay. That's zero union with. One to the
i or greater than = zero. That's the
strings of all one. So there's a set at
this expression to nodes. And for our last
example, let's think about zero + one.
Now, that iterated. Okay? So, we put the
star around the union of the two
individual character instead of having the
star on each character individually in
taking the union of the two things. So
what is the, what is this expression equal
to? Well, let's work with the definition
of star. So, we know. That this is the
union over i greater than or equal to zero
of zero + one to the i. And what does that
look like, well, that looks like first of
all, there's the empty string, right? And
then another string in this language is,
is. Excuse me, is drawn from zero + one
and so this, I shouldn't say another
string but another set of strings is the
language zero + one. And then zero + one
concatenated with itself, okay? And in
general, is going to be zero + one
concatenated by itself i times. Now what
does that mean? That means that every
position, if we have a string of length i,
at every position we could pick a zero or
a one to plug in and this works for any
length string. This is gonna be true of
strings of every length and so in fact
this language is just going to be all
strings Of 0's and 1's. In fact, what that
means is this, is the cycle effect on our
alphabet. Our alphabet that consists of
zero and one and so this is the set of all
strings that you can form over the entire
alphabet, And that has a special name when
that happens when you have a regular
expression that denotes the set of all
strings you can form out of the alphabet,
we write that as sigma star, okay? So just
meaning that all the strings of the
alphabet integrated as many times as you
like One last point I wanna make on this
before we go on here is that there are
actually lots of ways to write each of
these different languages. There's not a
unique way to write these. So for example,
let's just take this language here. The
second one that we did, and let me switch
colors. Another alternative way to write
this since we know the meaning of it is
these two strings one, one and one zero, I
could have written it as one, one. + one
zero and that would mean exactly the same
thing. We used two expressions denote
exactly the same set similarly with one
star, I could write this as one <i>. + one.</i>
And cuz this wouldn't change anything.
Adding in the single string one wouldn't
change anything since one is already
included in one<i>. This might be kind of a</i>
silly way to write that set but it doesn't
matter it has a meaning and it means
exactly the same things as one<i>. The point
again is that there is more than one way</i>
to write down the same set to write, to
write, you can write multiple regular
expressions that denote the same set.
Well, it come to the end of this video.
And to summarize, we looked at regular
expressions. Which are used to define
regular languages? And the regular
expressions are syntax, that's the.
Expression that we write down and if it
notes a set of strings which is the
regular language and that's the meaning of
the regular expression. And there are five
kinds of regular expressions in the
standard definition. There's an expression
for the empty string and that's denoted by
epsilon and then we have all the one
character strings and then there are three
compound expressions. Ways of building new
regular expressions from other regular
expressions and these are union,
concatenation, and iteration.