Re: Proving a Language Is Not a CFL

Bernd L 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?

That's not the regex that gives the result. Another one gives a
well-known non-CFL.
.

Relevant Pages

  • context free languages under SCRAMBLE operation
    ... For strings w and t, write w =' t if the symbols of w are a permutation of the symbols of t. ... which accepts the regular language to be scrambled can simply have its state transitions re-arranged to accept the SCRAMBLE of the language. ... This is de facto context free since every regular language is in turn context free. ...
    (comp.theory)
  • Re: Schildt
    ... intersection of a language is a language. ... Algol 60 and Algol 68? ... By looking at the syntax? ...
    (comp.lang.c)
  • Re: Proving a Language Is Not a CFL
    ... If A is a CFL and B is a regular language, then the intersection of A ... and B is context free. ...
    (comp.theory)
  • Re: 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)
  • 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)