Well, now we're going to, just briefly
take a look at the relationship between
the symbolic method and, formal languages
from, computer science.
So, and probably, for people, that have
studied, formal languages.
These kinds of questions have, have
occurred.
So formal language is a set of strings and
natural question is, how many strings of
length n are there in a given language?
Well, and the answer is, that we can use
an OGF to enumerate them and we can
essentially use the symbolic method, or
view the symbolic method as an approach to
solving this problem.
It's a very systematic way to solve
problems like this.
Now, there's an issue when it comes to
counting, that has to do with ambiguity.
Typically in a formal language we're just
concerned about specifying the set and it
could be that there's more than one way to
derive a particular string.
Now, that's a key issue in understanding
formal languages and building compilers
and other things like that.
The so if there's more than one way to
derive a string we're going to count
really all the ways to derive the string.
So we want to work with unambiguous
languages.
Now without getting into detail of the
study of ambiguity for all formal
languages I'm just going to give some
examples.
Examples.
So let's look at regular expressions.
So a regular expression, uses the,
concatenation or the or, the
star[UNKNOWN], operation to, specify a
formal language.
And if you're no familiar with regular
expressions, go read up on them and then
come back to this.
In, the theorem which is really The same
as what we did for the symbolic method,
but just a different notation, is if
you've got that enumerating OGS for, two
RVs, then you take the or.
Then the OGS is the sum.
If you take the concatenation the OGS is
the product.
And if you take A star, it's one over one
minus.
And it's really, the same proof.
The symbolic method with different
notations as long as our theories are
unambiguous.
So, one thing this says is that the OGF
for an unambiguous RE is rational because
all you get out of here is the ratio of
two polynomials no matter how,uh Apply,
these operations, you're going to get the
ratio of two polynomials, for the, OGF.
So, just to kind of highlight the point,
another way to say this is that OGFs that
enum, enumerate regular languages are
rational.
So that is language, a language, regular
language it's a there's exist and already
doesn't necessary have to be unambiguous.
But there's a construction, a well known
construction.
That gives an unambiguous regular
expression for any regular language.
One way to define a regular language is if
there exist a finite state automatom out
for the language.
And then Kleene's theorem, Yes, if you
look at the detail of Kleene's theorem it
takes a finite state machine and gives a
regular expression that is unambiguous.
So and then if that's an umambiguous RE
then it's rational.
So, that's just a quick look at the,
landscape with regular expressions.
And it's, it's a kind of a fun way to,
think about, numeration problems, because
people are maybe more used to, regular
expressions, ...um, but there is the issue
of, ambiguity.
So like we did binary strings with, no
zeros, this is, that derivation in regular
expression language.
So that's an RE for binary strings with,
no zero, zero, zero, an unambiguous one.
And then just applying, the theorem, it's,
going to be the, for the stars 1 over 1
minus, uh...
And for, the tail part, it's just, it's
just that, it's pretty much, the same,
ratio of two polynomials, that we had, in
the case, when, when we did it using the
symbolic method, we get the same result,
of course.
And again expanded, in the same way.
Here's another example.
What about binary strings that represent
multiples of 3?
This is a famous example of, say, of
finite state machine.
With three states, you can, you can,
derive a finite state machine for this.
Or you can get.
This regular expression.
And, ug, again, that's about regular
expressions.
In believe that this is multiples of
three.
But that's the one.
This is three, six, nine, twelve, fifteen,
and so forth.
So how many binary strings represent
multiples of three.
Oh, we can just apply the theorem to that,
regular expression.
And we get, this, rational function.
And, after a while, we can, simplify down
to, that, simple ratio of 2, 2
polynomials.
And this one actually expands explicitly
with, partial fractions.
It's going to be asymptotic to 2 to the n
minus 1 over 3.
And that's what you'd expect.
You always have a one bit and then you get
2 to the N minus 1 possibilities and a
third of them are going to be multiples of
3, approximately.
This is minus 1 to the N to make it come
out exactly, but this is a fine example of
enumerating regular languages.
So it's just the symbolic method in
different notation.
So similarly, for context free languages
where we have non-terminals and we use or,
or can[INAUDIBLE], again, the same idea.
Works.
As for the symbolic method, the key is to
make sure that it's unambiguous.
And now it's a more complicated situation
because we have multiple equations and
there's a discussion in the text about the
idea that OGFs that enumerate context free
grammar's are algebraic.
So an algebraic function is a function
satisfies the polynomial equation's
coefficients or polynomials with rational
coefficients.
And again it's just a natural follow on
from just the basic rules that we're using
to develop these generating functions.
Now, The, actually the constructions that
we've considered are all, unambiguous
context free grammars, just using
different notation.
So that's binary trees.
But this is binary trees as a context
free, grammar.
And so then the o g f is going to satisfy
just an algebraic function.
Because it's a solution to an equation
like that can be recursive.
So this is for bit strings and it's a
little more complicated to represented as
a c f g.
But not that, not that big a story.
Really it's just different notation.
And bit stream from those 0, 0 and so
forth, so, now, because of ambiguity not
all context free corresponds to common to
our classes that we can innumerate in this
way.
And not all construction that we consider
in a symbolic method are contact free
grammar because there's other operations
that we use, besides just the, Of
incandation and or of this many, many
other operations that we use that make the
combinatorial classes that we're talking
about different from content-free gram is
typically but still there's lot of cases
where its the same thing.
And in those cases you know, it's
worthwhile to be aware of that.
So this is just an example for the study
of random walks.
So a walk is a sequence of plus and minus
characters.
And there's lots of implic, applications
of random walks.
And so called gamblers rune problems.
And also the study of some sorting
algorithms, these are discussed in the
text.
So in a just from the idea of a secret of
plus and minus characters, there's all
kind of natural questions that arise like.
How many different walks of length n are
there?
Or how many different walks of length n
are there where every pre, pretext has
more pluses than minuses?
That is it stays above the line because
you're all, you're going plus more than
you go minus at all ways.
And similar questions like that are
studied in the all different types of
applications.
It's a relatively general framework.
And so the key to studying random walks in
this context is to come up with an
unambiguous way to decompose them.
So that's a typical walk.
And here's one way to come up with that
unambiguous decomposition.
First one is, is to consider of the class
u where the walk always stay above the
line, always, got more pluses than
minuses, so you can make a u by either
just taking a plus or by having a u.
And then appending another u to it, and
then having a minus.
So it starts at, at the baseline with the
plus and it ends at plus 1 and never hits
0.
That's a u.
And that's a unambiguous way to define a
u.
And similarly, you can have a d.
It starts with minus end in minus 1 never
hits zero and you get a d by putting two
d's together.
And then what those are good for is that
they give a way to define a random walk
that begins at zero and ends at zero.
So either it's a u that takes another
minus to get at zero.
And then you have one that begins at zero
and ends at zero.
Or the first step is down and you have a d
and then you go up and then have another
s.
So this is a context free grammar, just
using these three constructions that's an
un, unambiguous decomposition of a random
walk that starts at the origin and ends at
the origin.
Okay.
And that construction then, uh,[COUGH]
that's a context-free language.
Then we can use this symbolic language to
get, generated functions equations.
This time there's three equations, and
these three unknowns.
In solving those equations simultaneously
they're like the tree equation actually
and the end result is that the number of
such walks is 2N choose N.
There's lots of easier ways to prove this
result, but the approach generalizes to
cover many similar more difficult problems
you can read about.
In the text.
So that's context-free languages counting
in context-free languages using the
symbolic method.
Next we'll look at Tries.