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, probably for people that have studied formal languages, then these kind of questions have occurred. So a formal language is a set of strings, and the natural question is how many strings of length n are there in a given language. Well and the answer is, that we can us 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. Now typically in a formal language, we're just concerned about specifying the set and could be that more than one way to derive a particular string and that's a key issue in understanding formal languages in Boolean compilers and other things like that. 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 the study of ambiguity form of formal languages. I just going to give some examples. So lets look regular expressions. So a regular expression uses the operation to specify a formal language. And if you're not familiar with regular expressions, go read up on them and then come back to this. And the theorem, which is really the same as what we did for the symbolic method, but just with different notation, is if you've got enumerating OGFs for two REs And you take the or, then, or GF is the sum, if you take the concatenation, the OGF is the product, and if you take A star, it's 1 over 1 minus. And it's really the same proof, as the symbolic method with different notation. As long as the REs are unambiguous. So one thing that this says is that, the OGF for an unambiguous RE is rational. because all you get out of here is a ratio of two polynomials no matter how you 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 that OGF that enumerate regular languages are rational. So that is a language regular language is in the existence or it does necessarily A and B ambiguous. But there is a construction well known construction that gives an ambiguous regular expression for any regular language. One way to define a regular line which is that there exists a finite state automaton for the language. And then Kleene's theorem is if you look at the details of Kleene's theorem, it takes a finite state machine and gives a regular expression that is unambiguous. So, and then if there's an unambiguous R even, it's rational. So that's just a quick look at the landscape with regular expressions. And it's kind of a fun way to think about enumeration problems because people maybe are more used to regular expressions. But there is the issue of ambiguity. So like we did binary strings with no 0s, this is that derivation in regular expression language. So that's an RE for binary strings, with node 0,0,0. An unambiguous one, and then just applying the theorem, it's going to be the for the stars, 1 over 1- and for the tail part, it's just that. It's pretty much the same ratio of two polynomials that we had in the case when we did it using a 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 three? This is a famous example of, let's say, a finite state machine with three states you can derive a finance statement sheet for this or you can get this regular expression. And again that’s about regular expressions to believe that this is multiples of three but that’s the one this is 3, 6, 9, 12, 15 and so forth. So how many binary strings represent multiples of 3? Well, you just apply the theorem to that regular expression and we get this rational function, and then after a while, we can simplify down to that simple ratio of two polynomials. And this one actually expands explicitly with partial fractions. It's going to be asymptotic to 2 to the n- 1 over 3. And that's what you'd expect. You always have a 1 bit, and then you got 2 to the n- 1 possibility and a third of them are going to be multiples of 3, approximately. There's a 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, similarity for context free languages. Where we have nonterminals and we use or, or concatenation. 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 grammars are algebraic. So an algebraic function's a function satisfies a polynomial equation whose coefficients are polynomials with rational coefficients. And again, that's just a natural follow on from just the basic rules that we're using to develop these generating functions. Actually, the constructions that we've considered are all unambiguous context free grammar. It's just using different notation. So that's binary trees, but this is binary trees as a context free grammar And so then the OGF is going to satisfy. [COUGH] It's an algebraic function because it's a solution to an equation like that can be recursive. So this is for bitstrings and it's a little more complicated to represent it as a CFG but not that big a story. Really it's just different notation. And bit strings from those 00 and so forth. So now because of ambiguity, not all context free grammar correspond to combinatorial classes that we can enumerate in this way. And not all constructions that we consider in a symbolic method are context-free grammars because there's other operations that we use besides just, Concatenation and or, there's many, many other operations that we use that may be common to our classes that we're talking about. Different from context free grammars, typically. But still, there's lot of cases where it's the same thing. And in those cases, 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 applications of random walks and so-called gambler's ruin problems. And also the study of some sorting algorithms, these are discussed in the text. So just from the idea of a sequence of plus and minus characters, there's all kinds of natural questions that arise, like how many different walks of length are there, or how many different walks of length are there where every pretext has more plusses than minuses? That it stays above the line because you're going plus more than you're going minus, always. And similar questions like that are studied in 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 the unambiguous decomposition. First one is to consider the class U where the walk always stays 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 it at the baseline with the plus and it ends at +1, never hits 0, that's u. And that's an unambiguous way to define a U and similarly you can have a D that's starts with minus, ends with 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 0 and ends at 0. So either it's a U that takes another minus to get it 0, and then you have one that begins at 0 and ends at 0. Where 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 unambiguous decomposition of a random walk that starts with the origin and ends in the origin. And that construction then, [COUGH] that's a context free language. Then we can use the symbolic method to get generating functions equations. This time it's three equations in these three unknowns. And solving those equations simultaneously. They're like the Tree equations actually, and the end result is that the number of such walks is 2N. 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 context-free languages using the symbolic method. Next we'll look at tries.
