Re: Proving a Language Is Not a CFL

Bernd L <berndlosert@xxxxxxxxx> writes:

This is a problem from Sipser's book which I'm unable to answer:

If A is a CFL and B is a regular language, then the intersection of A
and B is context free. Given this result, show that the language C =
{w : w in {a, b, c}* and contains an equal number of a's, b's and c's}
is not a CFL.

Let D be the language described by the regex (abc)*. This language is
regular and is a subset of C so the intersection of C and D is D which
is also context free. What gives?

You have the logic backwards. The statement one is to assume is that:

(A is CF) and (B is regular) => (A /\ B) is CF.

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?

--
Ben.
.

Relevant Pages

  • Re: pumping lemma for CFL
    ... >> resulting string is in L. ... > not the regular language version. ... yes i am wanting to understnad the CFL pumping lemma exists string in L ...
    (sci.math)
  • Re: pumping lemma for CFL
    ... If some language L is regular, then there is some number p (pumping ... resulting string is in L. ... Quite often, even if you pick your test string carefully, the CFL version will require checking a bewildering number of possible cases and making sure you've covered all the bases, as it were, getting a contradiction in every possible case. ...
    (sci.math)
  • Re: A CFG for a CFL
    ... >> The language ... regular, but for a given alphabet A, if |A|> 1 then the language ... > You want a CFL over the alphabet ...
    (comp.theory)
  • Proving a Language Is Not a CFL
    ... If A is a CFL and B is a regular language, then the intersection of A ... is not a CFL. ...
    (comp.theory)
  • Re: Armenian, Sumerian, Burushaski, and Turkic languages
    ... indicating the importance of finding regular changes. ... There are certainly plenty of known regular correspondences ... Note that due to sporadic language change, ... sound changes, large variance in what counts as "similar"), you're ...
    (sci.lang)