Context Free Grammars and Languages Formal Definition

[00:00:01]in this video I'm going to describe and formally define context free grammars and context free languages let's begin by looking at an example context free grammar here we see several Productions sometimes we call them rules and we see some non-terminals and some terminal symbols uh in this example our non-terminal symbols are e t and F you can tell their non-terminals because they appear on the left- hand side of rules on the right hand side of rules we have both non-terminals like ENT and terminals like the plus the multiplication and the parenthesis and a terminal symbol called a here we're using a shorthand for writing multiple rules on one line and this is very common the vertical bar here shows two different rightand sides and it's nothing more than shorthand for two separate Productions so what does a context free grammar have every context free grammar has variables terminals rules and a start variable one of the variables is distinguished as the start variable uh generally it's uh s and uh we assume that the first non-terminal on the first rule the left hand side of the first rule by default is the start symbol so in our previous example e is assumed to be the start symbol the start variable variables are sometimes called uh non-terminals and I try to use the term non-terminals as much as I can terminals are uh symbols from the alphabet so we're describing languages here and the fundamental symbols which we string together are symbols from the alphabet in some examples they're individual letters like pen and a and in other context fre grammars they're a little bit more complex in a programming language grammar we use the term tokens for the terminals so the context fre grammar creates a string of tokens or describes legal strings of tokens and the tokens themselves are more complex generally described by regular expression and can consist of sequences of of character such as identifiers and so on the context fre grammar has a number of rules and these are sometimes called Productions uh occasionally you'll see this notation instead of the arrow e goes to e plus e colon colon equal is a more traditional symbol for context free grammar Rule and if you see that symbol you know you're dealing with a context free grammar if you see just an arrow well it could be all kinds of things but in our examples it'll indicate rules or Productions in the grammar next let's talk about how we can use a context fre grammar to generate a string of symbols here's our grammar our sample grammar again and here is a derivation so with a derivation you start with the starting symbol in this case it's e and at each step you apply one of the rules to change the form making it longer and longer until ultimately you're left with a string of only terminals so we can see that we began by replacing e with e plus T using the first rule e goes to e plus T then we replace T sorry then we replaced e again but this time we use the second rule with t e is replaced by T and in the third step we replace t with an f and we keep going replacing and replacing until ultimately we end up with a string of terminals so this tells you that this string of symbols is in the language that's described by this context free grammar we could stop part way through for example at this step and we find we've got a string with some terminals like a plus pin and some non-terminals like T and F so this is what's called a sentential form and in our derivation on the way from the start symbol to the final string of terminals we have a number of different sentential forms now this these derivations can be lengthy and so often times we use this notation with a star to say that it goes from one sentential form to another sentential form in zero or more steps okay so this line right here describes our entire derivation all the way from e to the string here's another example of this notation where we're going from E we do a few steps and we get this sentential form which is right here in our derivation and then we do one more step in the derivation from here to Here by expanding the E using the rule that e goes to T and then we do zero or more and we finally end up with a sentential form that contains only terminal symbols in our derivation up here notice that whenever we chose to expand one of the non-terminals using one of the rules we always chose the leftmost non-terminal at this step in the first step there was only one non-terminal in the second step we could have expanded e or t but we chose the leftmost one we expanded e and again we chose T to expand this T and not that t and then we chose F to expand and so on always choosing at every step the non-terminal in the sentential form that is to the left that's a particular kind of derivation that we call a leftmost derivation we always choose the leftmost variable in the sentential form to expand and we can also Define rightmost derivation the same way we always choose the rightmost variable so here's a sentential form F goes to f plus T we expand the F to a here we chose in the rightmost derivation to expand T instead to an F but notice that regardless of which one you do first you end up with the same thing in the end okay you always end up with the same string in the end so there's a correspondence between a leftmost derivation and a rightmost derivation derivation here's our grammar again and here's a sample string that we're able to produce with this grammar for every leftmost derivation of this string there's exactly one rightmost derivation and for every rightmost derivation there's exactly one leftmost derivation now it may be that there are several different leftmost derivations to derive this string there might be 17 different ways to derive a particular string with leftmost derivations and that means there are 17 different ways to derive it with the rightmost derivation so whether we do a rightmost derivation or leftmost derivation um is not really that important we could also expand our non-terminals in no particular order and then we have something that's a derivation a legal derivation but that's not a rightmost and not a leftmost derivation so for that reason the parse tree is particularly useful because a parse tree abstracts away the order in which we chose our non-terminals to expand here is a parse tree sometimes called a derivation tree for the same string reading off the leaves we see a plus pin a * a pin so we read the leaves in exactly the same in order and um uh we see that the terminal string is uh exactly the string that we're deriving right here and we also see which rules are applied our first rule our first step in the derivation took e to e+ T and we can see the sentential form here and then we expanded this e with the rule e goes to T and we expanded this t with the rule T goes to F which order we do them in is abstracted away in the parse tree we only see which rules were used and where they were used not when they were used here's our grammar again and I just want to reiterate that we get the same result regardless of what order we apply the rules in what matters is which rule we choose to use and where we use it not when we use it in this derivation of f plus T we're going to uh a plus a and we're choosing to expand the F first using the rule uh F goes to a and then we're choosing to expand the T using the rule T goes to F and then F goes to a down here we're doing the T first instead of this F we're doing this T first and we're expanding to f um and then to a and then finally we're doing that first F expanding it doesn't matter which order you do these derivations all that matters is which rules you're using and where you're using them so that's the benefit of the parse tree because you lose the information about when but not where or what here's a parse tree for this particular derivation if we take a slice through the parse tree we get a sentential form if we take a slice here we get f plus T and that's the sentential form that we're starting with f plus T and as we sort of derive down we move this slice down until we've got nothing but terminal symbols so the par Tre abstracts away the actual order in which the rules are used it only remembers which rules were used now let's give the formal definition of a context free grammar it is a for Tuple consisting of variables the alphabet the rules and the start variable so to be more specific a grammar a context fre grammar is a four tle consisting of the set of variables which I prefer to call the set of non-terminals Sigma is the set of terminals okay the the symbols from the alphabet okay and in particular notice that V and sigma should be disjointed in other words their intersection should be empty there should be no symbols that are both variables and terminals okay if you look at a symbol it ought to be clear whether it's a variable or terminal and typically uh we don't go to the trouble of spelling out what these two sets are we just look at the rules if some symbol appears on the left hand side of a rule then by definition it is a non-terminal symbol and every other symbol that appears in the rules by default is a terminal symbol both sets are finite sets and generally fairly small then we have a set of Productions a set of rules and finally we have to identify which of these rules uh which of these non-terminals is the starting non- terminal and when we write our rules down on paper the uh procedure is to write uh the the starting symbol uh down first and Define it first now we get to two very important definitions the language of a grammar is the set of strings made up of terminal symbols such that starting with the start symbol we can derive that string okay to say this another way any string that we can derive with a grammar is in the language of that grammar a grammar defines a language remember that a language is a set of strings the strings themselves have to be finite in length languages in general are infinite sets of strings so that means in a language generally will'll have some short strings and some very long strings and some arbitrarily large strings since it's an infinite set the only way we can have an infinite set of strings is by allowing longer and longer and longer strings so if you give me a length then if the set if the language is infinite then if you give me a length there will be a string of that L of that length or greater in the language so a language is just a set of strings and the language of a particular context free grammar is a set of strings that can be derived from the start symbol a context free language is a language by definition that's generated by a context free grammar so that is the defin definition of what a context free language is if there is a context free grammar to describe that language then it is a context free language we may not know what the grammar is but the language itself can still be context free it may be difficult to find the grammar for the language but the language is context free if and only if there exists at least one context free grammar to describe it and I should note that given a particular context free language there can be many many context free grammars that describe it you can always add unnecessary rules that aren't ever used or applicable and get a slightly different grammar so there are an infinite number of context free grammars for every context free language we would like to have a small easy to understand grammar but those are particular difficult to uh discover the bottom line is that if there is a context free grammar to describe the language then the language is context free otherwise it is not now let's look at an example context free grammar here is our grammar it consists of three rules 1 23 S goes to PR s PR s goes to SS and S goes to Epsilon in this example we see that the right hand sides uh consist of a string of Terminals and non-terminals and that string of symbols can be empty so occasionally in grammars you'll see an Epsilon on the right hand side of a rule and we can see by definition uh there's only one uh uh non-terminal in this grammar so it must be the start symbol uh and it is s what does this thing generate well it generates the empty string clearly and then you could use the first rule and then let s go to Epsilon and that would give you PR PR and uh if you kind of analyze this thing uh you can see that for every time you generate a left print you'll generate a right print somewhere to the right of it and this rule says you can sort of generate lots of different combinations and this is the language that's generated by it uh or at least I'm sketching out the language the language is the set of parentheses where you have the parentheses being balanced in the traditional uh way that we balance them in in U arithmetic Expressions a lot of times in complicated expressions like this in when I'm programming or whatever and I get confused if I've got it on paper I can draw a line from one the opening parentheses to the matching closed parentheses here is another example context free grammar the rules that uh describe this language are s goes to Epsilon and S goes to 0 S1 if you think about it for every zero you generate on the left hand side you generate a one on the right hand side here's a sample pars tree for a string and you see that s goes to 0 S1 and this s goes to 0 S1 and so on so you get a string of zeros followed by a string of ones such that the number of zeros is exactly the same as the number of ones at the bottom and I didn't draw this very well uh in fact s goes to 0s1 and then the final s goes to Epsilon also in this uh drawing of the Parry I have uh pulled all the leaves down a bit so that you can see what the string of terminal symbols is more easily here is the language expressed in different notation 0o to the n 1 to the N now elsewhere I use the pumping limma to show that this language is not a regular language so we've given a context free grammar for this language and therefore this language is a context free language so we've shown that the regular languages are a subset and it's a proper subset of the context free languages every regular language is a context free language but there are many many context free languages which are not regular