1
00:00:00,012 --> 00:00:06,018
Well, now we're going to, just briefly
take a look at the relationship between

2
00:00:06,018 --> 00:00:11,935
the symbolic method and, formal languages
from, computer science.

3
00:00:11,936 --> 00:00:18,372
So, and probably, for people, that have
studied, formal languages.

4
00:00:18,373 --> 00:00:22,246
These kinds of questions have, have
occurred.

5
00:00:22,247 --> 00:00:28,674
So formal language is a set of strings and
natural question is, how many strings of

6
00:00:28,674 --> 00:00:34,920
length n are there in a given language?
Well, and the answer is, that we can use

7
00:00:34,920 --> 00:00:40,624
an OGF to enumerate them and we can
essentially use the symbolic method, or

8
00:00:40,624 --> 00:00:46,438
view the symbolic method as an approach to
solving this problem.

9
00:00:46,438 --> 00:00:50,199
It's a very systematic way to solve
problems like this.

10
00:00:50,199 --> 00:00:55,712
Now, there's an issue when it comes to
counting, that has to do with ambiguity.

11
00:00:55,712 --> 00:01:01,997
Typically in a formal language we're just
concerned about specifying the set and it

12
00:01:01,997 --> 00:01:06,575
could be that there's more than one way to
derive a particular string.

13
00:01:06,575 --> 00:01:11,894
Now, that's a key issue in understanding
formal languages and building compilers

14
00:01:11,894 --> 00:01:16,305
and other things like that.
The so if there's more than one way to

15
00:01:16,305 --> 00:01:21,514
derive a string we're going to count
really all the ways to derive the string.

16
00:01:21,514 --> 00:01:24,762
So we want to work with unambiguous
languages.

17
00:01:24,762 --> 00:01:29,088
Now without getting into detail of the
study of ambiguity for all formal

18
00:01:29,088 --> 00:01:32,395
languages I'm just going to give some
examples.

19
00:01:32,396 --> 00:01:36,134
Examples.
So let's look at regular expressions.

20
00:01:36,134 --> 00:01:41,347
So a regular expression, uses the,
concatenation or the or, the

21
00:01:41,347 --> 00:01:46,334
star[UNKNOWN], operation to, specify a
formal language.

22
00:01:46,334 --> 00:01:52,039
And if you're no familiar with regular
expressions, go read up on them and then

23
00:01:52,039 --> 00:01:56,373
come back to this.
In, the theorem which is really The same

24
00:01:56,373 --> 00:02:01,271
as what we did for the symbolic method,
but just a different notation, is if

25
00:02:01,271 --> 00:02:05,881
you've got that enumerating OGS for, two
RVs, then you take the or.

26
00:02:05,881 --> 00:02:09,867
Then the OGS is the sum.
If you take the concatenation the OGS is

27
00:02:09,867 --> 00:02:13,243
the product.
And if you take A star, it's one over one

28
00:02:13,243 --> 00:02:16,081
minus.
And it's really, the same proof.

29
00:02:16,081 --> 00:02:21,521
The symbolic method with different
notations as long as our theories are

30
00:02:21,521 --> 00:02:25,592
unambiguous.
So, one thing this says is that the OGF

31
00:02:25,592 --> 00:02:31,767
for an unambiguous RE is rational because
all you get out of here is the ratio of

32
00:02:31,767 --> 00:02:38,607
two polynomials no matter how,uh Apply,
these operations, you're going to get the

33
00:02:38,607 --> 00:02:46,002
ratio of two polynomials, for the, OGF.
So, just to kind of highlight the point,

34
00:02:46,003 --> 00:02:52,550
another way to say this is that OGFs that
enum, enumerate regular languages are

35
00:02:52,550 --> 00:02:57,740
rational.
So that is language, a language, regular

36
00:02:57,740 --> 00:03:04,481
language it's a there's exist and already
doesn't necessary have to be unambiguous.

37
00:03:04,482 --> 00:03:08,768
But there's a construction, a well known
construction.

38
00:03:08,769 --> 00:03:13,971
That gives an unambiguous regular
expression for any regular language.

39
00:03:13,972 --> 00:03:19,746
One way to define a regular language is if
there exist a finite state automatom out

40
00:03:19,746 --> 00:03:24,548
for the language.
And then Kleene's theorem, Yes, if you

41
00:03:24,548 --> 00:03:30,358
look at the detail of Kleene's theorem it
takes a finite state machine and gives a

42
00:03:30,358 --> 00:03:36,503
regular expression that is unambiguous.
So and then if that's an umambiguous RE

43
00:03:36,503 --> 00:03:41,587
then it's rational.
So, that's just a quick look at the,

44
00:03:41,587 --> 00:03:47,867
landscape with regular expressions.
And it's, it's a kind of a fun way to,

45
00:03:47,868 --> 00:03:54,465
think about, numeration problems, because
people are maybe more used to, regular

46
00:03:54,465 --> 00:03:59,051
expressions, ...um, but there is the issue
of, ambiguity.

47
00:03:59,051 --> 00:04:04,751
So like we did binary strings with, no
zeros, this is, that derivation in regular

48
00:04:04,751 --> 00:04:09,306
expression language.
So that's an RE for binary strings with,

49
00:04:09,306 --> 00:04:16,194
no zero, zero, zero, an unambiguous one.
And then just applying, the theorem, it's,

50
00:04:16,195 --> 00:04:19,826
going to be the, for the stars 1 over 1
minus, uh...

51
00:04:19,827 --> 00:04:28,267
And for, the tail part, it's just, it's
just that, it's pretty much, the same,

52
00:04:28,267 --> 00:04:34,882
ratio of two polynomials, that we had, in
the case, when, when we did it using the

53
00:04:34,882 --> 00:04:38,958
symbolic method, we get the same result,
of course.

54
00:04:38,958 --> 00:04:43,946
And again expanded, in the same way.
Here's another example.

55
00:04:43,946 --> 00:04:47,673
What about binary strings that represent
multiples of 3?

56
00:04:47,673 --> 00:04:51,897
This is a famous example of, say, of
finite state machine.

57
00:04:51,897 --> 00:04:57,146
With three states, you can, you can,
derive a finite state machine for this.

58
00:04:57,146 --> 00:05:00,256
Or you can get.
This regular expression.

59
00:05:00,256 --> 00:05:03,799
And, ug, again, that's about regular
expressions.

60
00:05:03,799 --> 00:05:06,760
In believe that this is multiples of
three.

61
00:05:06,760 --> 00:05:11,131
But that's the one.
This is three, six, nine, twelve, fifteen,

62
00:05:11,131 --> 00:05:14,731
and so forth.
So how many binary strings represent

63
00:05:14,731 --> 00:05:19,013
multiples of three.
Oh, we can just apply the theorem to that,

64
00:05:19,013 --> 00:05:23,996
regular expression.
And we get, this, rational function.

65
00:05:23,996 --> 00:05:29,882
And, after a while, we can, simplify down
to, that, simple ratio of 2, 2

66
00:05:29,882 --> 00:05:33,967
polynomials.
And this one actually expands explicitly

67
00:05:33,967 --> 00:05:38,517
with, partial fractions.
It's going to be asymptotic to 2 to the n

68
00:05:38,517 --> 00:05:42,179
minus 1 over 3.
And that's what you'd expect.

69
00:05:42,180 --> 00:05:47,410
You always have a one bit and then you get
2 to the N minus 1 possibilities and a

70
00:05:47,410 --> 00:05:51,439
third of them are going to be multiples of
3, approximately.

71
00:05:51,439 --> 00:05:56,685
This is minus 1 to the N to make it come
out exactly, but this is a fine example of

72
00:05:56,685 --> 00:06:01,558
enumerating regular languages.
So it's just the symbolic method in

73
00:06:01,558 --> 00:06:08,768
different notation.
So similarly, for context free languages

74
00:06:08,769 --> 00:06:18,954
where we have non-terminals and we use or,
or can[INAUDIBLE], again, the same idea.

75
00:06:18,955 --> 00:06:22,828
Works.
As for the symbolic method, the key is to

76
00:06:22,828 --> 00:06:30,538
make sure that it's unambiguous.
And now it's a more complicated situation

77
00:06:30,538 --> 00:06:38,378
because we have multiple equations and
there's a discussion in the text about the

78
00:06:38,378 --> 00:06:44,583
idea that OGFs that enumerate context free
grammar's are algebraic.

79
00:06:44,584 --> 00:06:49,373
So an algebraic function is a function
satisfies the polynomial equation's

80
00:06:49,373 --> 00:06:53,161
coefficients or polynomials with rational
coefficients.

81
00:06:53,162 --> 00:06:58,980
And again it's just a natural follow on
from just the basic rules that we're using

82
00:06:58,980 --> 00:07:05,466
to develop these generating functions.
Now, The, actually the constructions that

83
00:07:05,466 --> 00:07:10,796
we've considered are all, unambiguous
context free grammars, just using

84
00:07:10,796 --> 00:07:14,350
different notation.
So that's binary trees.

85
00:07:14,350 --> 00:07:18,516
But this is binary trees as a context
free, grammar.

86
00:07:18,516 --> 00:07:25,619
And so then the o g f is going to satisfy
just an algebraic function.

87
00:07:25,619 --> 00:07:31,144
Because it's a solution to an equation
like that can be recursive.

88
00:07:31,144 --> 00:07:37,401
So this is for bit strings and it's a
little more complicated to represented as

89
00:07:37,401 --> 00:07:41,212
a c f g.
But not that, not that big a story.

90
00:07:41,212 --> 00:07:47,176
Really it's just different notation.
And bit stream from those 0, 0 and so

91
00:07:47,176 --> 00:07:54,936
forth, so, now, because of ambiguity not
all context free corresponds to common to

92
00:07:54,936 --> 00:07:59,249
our classes that we can innumerate in this
way.

93
00:07:59,250 --> 00:08:06,912
And not all construction that we consider
in a symbolic method are contact free

94
00:08:06,912 --> 00:08:14,180
grammar because there's other operations
that we use, besides just the, Of

95
00:08:14,180 --> 00:08:19,710
incandation and or of this many, many
other operations that we use that make the

96
00:08:19,710 --> 00:08:25,635
combinatorial classes that we're talking
about different from content-free gram is

97
00:08:25,635 --> 00:08:30,483
typically but still there's lot of cases
where its the same thing.

98
00:08:30,483 --> 00:08:37,307
And in those cases you know, it's
worthwhile to be aware of that.

99
00:08:37,307 --> 00:08:42,664
So this is just an example for the study
of random walks.

100
00:08:42,665 --> 00:08:47,246
So a walk is a sequence of plus and minus
characters.

101
00:08:47,247 --> 00:08:52,859
And there's lots of implic, applications
of random walks.

102
00:08:52,859 --> 00:08:58,426
And so called gamblers rune problems.
And also the study of some sorting

103
00:08:58,426 --> 00:09:01,983
algorithms, these are discussed in the
text.

104
00:09:01,984 --> 00:09:07,675
So in a just from the idea of a secret of
plus and minus characters, there's all

105
00:09:07,675 --> 00:09:13,003
kind of natural questions that arise like.
How many different walks of length n are

106
00:09:13,003 --> 00:09:15,533
there?
Or how many different walks of length n

107
00:09:15,533 --> 00:09:19,286
are there where every pre, pretext has
more pluses than minuses?

108
00:09:19,287 --> 00:09:23,748
That is it stays above the line because
you're all, you're going plus more than

109
00:09:23,748 --> 00:09:27,363
you go minus at all ways.
And similar questions like that are

110
00:09:27,363 --> 00:09:30,761
studied in the all different types of
applications.

111
00:09:30,762 --> 00:09:37,569
It's a relatively general framework.
And so the key to studying random walks in

112
00:09:37,569 --> 00:09:42,811
this context is to come up with an
unambiguous way to decompose them.

113
00:09:42,811 --> 00:09:48,392
So that's a typical walk.
And here's one way to come up with that

114
00:09:48,392 --> 00:09:55,317
unambiguous decomposition.
First one is, is to consider of the class

115
00:09:55,317 --> 00:10:05,037
u where the walk always stay above the
line, always, got more pluses than

116
00:10:05,037 --> 00:10:13,965
minuses, so you can make a u by either
just taking a plus or by having a u.

117
00:10:13,966 --> 00:10:19,531
And then appending another u to it, and
then having a minus.

118
00:10:19,531 --> 00:10:27,056
So it starts at, at the baseline with the
plus and it ends at plus 1 and never hits

119
00:10:27,056 --> 00:10:28,440
0.
That's a u.

120
00:10:28,441 --> 00:10:32,866
And that's a unambiguous way to define a
u.

121
00:10:32,866 --> 00:10:39,307
And similarly, you can have a d.
It starts with minus end in minus 1 never

122
00:10:39,307 --> 00:10:43,604
hits zero and you get a d by putting two
d's together.

123
00:10:43,605 --> 00:10:49,738
And then what those are good for is that
they give a way to define a random walk

124
00:10:49,738 --> 00:10:54,932
that begins at zero and ends at zero.
So either it's a u that takes another

125
00:10:54,932 --> 00:10:58,653
minus to get at zero.
And then you have one that begins at zero

126
00:10:58,653 --> 00:11:02,222
and ends at zero.
Or the first step is down and you have a d

127
00:11:02,223 --> 00:11:05,178
and then you go up and then have another
s.

128
00:11:05,178 --> 00:11:10,080
So this is a context free grammar, just
using these three constructions that's an

129
00:11:10,080 --> 00:11:15,120
un, unambiguous decomposition of a random
walk that starts at the origin and ends at

130
00:11:15,120 --> 00:11:16,411
the origin.
Okay.

131
00:11:16,411 --> 00:11:21,915
And that construction then, uh,[COUGH]
that's a context-free language.

132
00:11:21,916 --> 00:11:27,909
Then we can use this symbolic language to
get, generated functions equations.

133
00:11:27,910 --> 00:11:32,760
This time there's three equations, and
these three unknowns.

134
00:11:32,760 --> 00:11:40,167
In solving those equations simultaneously
they're like the tree equation actually

135
00:11:40,167 --> 00:11:45,098
and the end result is that the number of
such walks is 2N choose N.

136
00:11:45,099 --> 00:11:51,012
There's lots of easier ways to prove this
result, but the approach generalizes to

137
00:11:51,012 --> 00:11:56,008
cover many similar more difficult problems
you can read about.

138
00:11:56,009 --> 00:12:03,852
In the text.
So that's context-free languages counting

139
00:12:03,852 --> 00:12:11,412
in context-free languages using the
symbolic method.

140
00:12:11,412 --> 00:12:14,685
Next we'll look at Tries.