This first question asks us to make a few statements about formal grammars.
Let's go over a little bit of vocabulary.
A language is simply a set of strings.
A regular language is a type of language.
In particular, it's a set of strings that can be represented by
a finite-state machine or a regular expression.
A context-free language is also a set of strings
but can be represented by context-free grammar,
and what these 3 questions are asking us in this problem
is to determine the relationship between a regular language and a context-free language,
so let's say this bubble represents the set of regular languages.
It's a set of sets of strings.
And let's say this blob is the set of context-free languages.
What we want to determine is how we can connect these two.
Is it the case that no regular languages are context-free languages and vice versa?
Or perhaps there are some regular languages that are not context-free.
There are some context-free languages that are not regular,
but there are some languages that are regular and context-free.
And the last 2 possibilities are that all regular languages are context-free and vice versa.
This kind of looks like a Pac-Man. Nom, nom.
As it turns out, this diagram is the correct one.
All regular languages are context-free, but not all context-free languages are regular.
Briefly in lecture, Wes outlined the proof that all regular languages are context-free.
The way the proof works is that you show that given an arbitrary
finite-state machine, you can create a context-free grammar
that embodies it, that represents the same functionality.
Namely, it generates the same exact set of strings,
and to show that there are some context-free languages that are not regular,
we just have to come up with an example.
An example of this is this set of matching parentheses.
As it turns out--and I'm not going to prove it here--you can't represent this language
with a regular expression.
That's because you can't count
how many times you see a left parentheses
and then require that you see exactly that many right parentheses.
There's just no form of counting in a regular expression.
You can't hold that much state.
Given that review, let's go over the actual questions.
If a language is regular, than that language is also context-free.
This is always true because we have our Pac-Man diagram here,
and also because you can take any regular language
and represent it with a context-free grammar.
You can take any finite-state machine and represent it with a context-free grammar.
If a language L is context-free, than that language L is also regular.
This is sometimes true.
If we have a regular language, that language is context-free,
and, well, it's also regular.
We have a case where sometimes a context-free language is regular.
The question is is this always true, and the answer is no.
If we have a context-free language such as the matching parentheses I went over before,
this is a language that's context-free, but it's not regular.
Sometimes this statement is true, and sometimes it's not.
If 2 context-free grammars, G1 and G2,
both accept an infinite number of strings, than they accept the same strings.
This is sometimes true.
Let's think of a couple examples.
Well, there's a straightforward example that shows
that this is a statement that can be true,
and that is when G1 and G2 are the same grammar.
Let's say we have the language ba* that Wes likes to use in the examples.
We have baaa, baaaaa.
All right, so we have ba*.
Let's say we have the grammar G2.
And you know what?
Let's make it the same exact language.
I have 2 grammars.
Both accept an infinite number of strings.
They happen to be the same strings, so this statement is sometimes true.
We didn't say G1 and G2 had to be unique.
You could also come up with examples where G1 and G2 are different,
but they're the same exact string, so you could do baa*.
And you'll also note I used a regular expression for my grammar,
but all regular languages are context-free, so this is perfectly acceptable.
Let's come up with a situation where this isn't true.
Let's change G2 so that instead of ba*
it's fa*, so we've got fa, faaa, and faa.
I don't know, a lot of a's.
These are both infinite, infinite grammars.
They're regular expressions, therefore, they're context-free,
but they don't accept the same strings, so we've come up with a case
where this can be true, and we come up with a case where it can be false,
so we're going to say it's sometimes true.