Re: Proving a Language Is Not a CFL

On May 4, 1:35 pm, Ben Bacarisse <ben.use...@xxxxxxxxx> wrote:
We are told to expect that not(C is CF). You show an example of D
that is regular and are surprised that (C /\ D) is CF but the
implication above is one way. It does not prohibit

not(C is CF) and (D regular) and (C /\ D) is CF

The theorem says that C's intersection with *all* regular languages is
CF. I image that you are expected to find one (or more) regular
languages whose intersection with C is clearly *not* a CFL. Does that
help?

I understand now. Thanks.
.

Relevant Pages