In this problem we've been asked to define a function, cfgempty,
which takes in a representation of a context-free grammar,
a starting state, and a list of visited states
and determines whether or not that context-free grammar is empty.
Just like regular languages, we define an empty grammar
as one that accepts no strings.
Worded the other way, the set of strings that the grammar accepts is empty.
So what's an example?
Say we have the grammar with symbol S and S goes to S with the terminal a.
In order for the grammar to make a string,
we have to be able to replace all of the non-terminals with terminals.
In this case, you can only replace S with itself and another terminal,
but you're never going to get to the point where the string that you're building up,
the substitutions you make, results in a string that's only terminals.
So we say this grammar is empty.
We want to write a program that does this for us because, well,
it can get pretty complicated.
As is the case with most of these examples,
we're going to use a recursive strategy.
As I said before, our procedure takes in 3 inputs:
the grammar, the symbol that we're on, and the symbols that we've visited.
This is important so that we don't loop forever.
An empty language is going to be one where we keep visiting the same states
over and over again without ever finishing.
So this is really crucial to making this function work.
We're going to go through the grammar,
visiting all the rules that apply and doing the rewrite,
and we're going to have 2 base cases.
One is that we visited this before, and this means we're going in a loop
and so this is a dead end.
We're going to return something that shows that this wasn't true.
We're going to return the value None.
That says that this grammar is indeed empty.
If the symbol is a terminal, then the grammar isn't empty,
or at least the grammar so far isn't empty.
We're just going to return the terminal because that's an example
where if you start from a terminal you get a terminal.
It's an example where the grammar finishes, it produces a string.
Otherwise, we're going to go through all the matching symbols,
all the rules that apply, do the substitutions, and recurse.
And if the recursion returns a not null value, it returns a string of terminals,
we're going to return the string back.
And if the grammar does accept any string,
we're going to build it up, going back up through the recursive calls
and return a string that is a member of this language.
Let's go to the IDE and write it out.
Here I've defined my function.
As we described earlier, we've taken a grammar
which is represented as a list of rewrite rules,
we have the symbol that we're currently on, and we have a list of symbols that we've visited.
If we've currently visited the symbol that we're on, we're going to return None.
We didn't find a string that's a member of this language,
and this is going to avoid infinite loops so that our program terminates.
So before I go on, you might have noticed I use the built-in function any,
which was given as a hint in the problem.
Let's briefly go over it.
Any takes in a list, and if any value in this list is true, any returns True.
It only returns False if all the values in this list are false.
Let's go back to the code.
Going back to our list comprehension, we're going to create a list of true and false values.
We're going to create a true value if there's a rewrite rule that applies to the symbol--
in other words, if there's a rewrite rule where the left-hand side
is the symbol that we're currently on.
Otherwise, it's going to be false.
This statement is essentially asking, "Is this symbol a terminal?"
If no rewrite rules apply, we're going to say it's a terminal.
And if it's a terminal, we're just going to return the current symbol we're on.
That's the base case that we decided to do when we were sketching out this program.
So those are our 2 base cases.
Now we have to write the code that goes through the rewrite rules
that apply to the non-terminal that we're on.
We're going to update the list of visited symbols with the current visit symbol.
Here we have a for loop that's going to go through every right-hand side of a rewrite rule
that applies to the current symbol.
This is going to give us every right-hand side
where the left-hand side is the symbol.
And the way it does that is it goes through the grammar,
and if the left-hand side is our symbol, it's going to return the right-hand side.
So this line asks the question, "Does every symbol in the right-hand side of our rule
"result in a non-empty grammar?"
And we determine that by calling cfgempty on every single symbol.
We're using a list comprehension to create a list of true or false values
that corresponds to whether the relative symbol is non-empty.
It's true if it's non-empty.
So if we're in the situation where we have a list of all true values,
that means every symbol in the right-hand side is non-empty
and the function all will return True in a similar way to any.
But all, as opposed to any, returns True only if every element in the list is true.
So if it's the case, we can get an example that proves that this context-free grammar
isn't empty.
So we create by going through each symbol in the right-hand side
and building up our string and then returning it.
If none of our rewrite rules terminated, then we're going to return None
because we didn't find anything down this path.