Intro to Context Free Grammars and Languages Video Lecture - Computer Science Engineering (CSE)

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 in this example our non-terminal
symbols are e T and F you can tell
they're 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 E and T and
terminals like the plus the
multiplication in 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 right-hand 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 generally it's s and 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 a previous example e is
assumed to be the start symbol or the
start variable variables are sometimes
called non terminals and I try to use
the term non terminals as much as I can
terminals are 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 paren and a and in other
context free grammars that are a little
bit more complex in a programming
language grammar we use the term tokens
for the terminals so the context
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 characters such as identifiers and so
on the context-free grammar has a number
of rules and these are sometimes called
productions 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 a 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-free grammar to generate a
string of symbols here's our grammar our
sample grammar again and here is a
derivation so with the 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 a plus T using
the first rule u goes to e plus T then
we replace T sorry then we replace T
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 paren 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
oftentimes 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
egos 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 could 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 the
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 derivation x'
to drive the string there might be 17
different ways to derive a particular
string with leftmost derivation x' and
that means there's 17 different ways to
drive it with the rightmost derivation
so whether we do a rightmost derivation
or a leftmost derivation 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 illegal derivation but it'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 with the a
plus paren a times a paren so we read
the leaves in exactly the same in order
and we see that the terminal string is
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 - E Plus T
and we can see the sentential form here
and then we expanded this e with it the
rule egos - T and we expand this T with
the rule T goes to F which order we do a
min 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 a plus a and we're
choosing to expand the F first using the
rule 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 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 wind 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 derived down
we move this slice down until we've got
nothing but terminal symbols so the
parse tree 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 four tuple
consisting of variables the alphabet the
rules and the starts variable so to be
more specific a grammar a context-free
grammar is a four tuple consisting of
the set of variables which I prefer to
call the set of non
terminals this Sigma is the set of
terminals okay the the symbols from the
alphabet okay and in particular notice
that V and Sigma should be disjoint 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 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 which of these non terminals
is a starting non-terminal and when we
write our rules down on paper the
procedure is to write the the starting
symbol 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 have some short strings
and some very long strings and some
arbitrarily large
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 that if the
language is infinite then if you give me
a length there will be a string of that
length 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 the 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 definite 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 particularly
difficult to 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 2 3 s goes
to print s print s goes to s s and s
goes to Epsilon
in this example we see that the right
hand sides consists 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
there's only one a non-terminal in this
grammar so it must be the start symbol
and it is s what does this thing
generate well it generates the empty
string clearly and then you can use the
first rule and then let s go to epsilon
and that would give you print prin and
if you kind of analyze this thing you
can see that for every time you generate
a left paren you'll generate a right
paren similar 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
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 way that we balance them in
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 open
parenthesis to the matching close
parentheses here is another example
context-free grammar the rules that
describe this language are s goes to
epsilon and s goes to 0 s 1 if you think
about it for every 0 you generate on the
left hand side you generate a 1 on the
right hand side here is a sample parse
tree for a string and you see that s
goes to 0 s 1 and this s goes to 0 s 1
and so on so you get a string of zeroes
followed by a string of ones such that
the number of zeroes is exactly the same
as the number of ones at the bottom and
I didn't draw this very
well in fact s goes to zero s1 and then
the final s goes to epsilon also in this
drawing of the parse tree I have 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
0 the N 1 to the N now elsewhere I use
the pumping lemma 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