Re: Proving a Language Is Not a CFL

Dnia 04-05-2008 o 17:34:58 Bernd L <berndlosert@xxxxxxxxx> napisał(a):

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?

Nothing. Try a different language.

HINT: Does it exist a regular language R, such that C \cap R = {a^n b^n c^n : n \in Nat} ?


mp
.

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: Find a new automata ,its language is only Recursive Lanauge.
    ... I would sure be interested in how you intend to guarantee that ... recursive constructs in a recursively enumerable language that create ... I can load a regular language into a PDA and it works ...
    (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: Proving a Language Is Not a CFL
    ... If A is a CFL and B is a regular language, ... A and B is context free. ... show that the language C ... is regular and is a subset of C so the intersection of C and D is D ...
    (comp.theory)
  • permutation of L
    ... Given a language L, let pbe the permutation of L, i.e. the set of ... Can someone give an example of a regular language L over ... context-free language. ...
    (comp.theory)