Re: Proving a Language Is Not a CFL

On May 4, 12:52 pm, "Michal Przybylek" <m...@xxxxxxxxxxxx> wrote:
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} ?

OK. I'm thinking of L(a*b*c*). That should work right?

.

Relevant Pages

  • 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)
  • 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: trying to use the pumping lemma
    ... Here is my proof using the pumping lemma. ... assume L is a regular language accepted by some DFA M of s states. ... is a string in L that is "long enough" (in your notation, ...
    (comp.theory)
  • Re: RegExp as Finite State Machine
    ... RegExp is a FSM, both describe a regular language. ... language it accepts is regular -- Regular Expressions. ...
    (comp.lang.javascript)
  • 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)