Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Context Free Languages, Pumping Lemma

  1. Mar 9, 2012 #1
    Hello fellow mathematicians/computer-scientists!

    I have a question:

    If a subset of a language is not context free, does that mean the language itself is not context-free?

    For example, I want to show that the following is not context free, using the pumping lemma:

    L = {[itex]\omega[/itex] [itex]\in[/itex] {a,b,c}* | [itex]\omega[/itex] has an equal # of a's, b's, and c's}

    And since T ={[itex]a^{n}b^{n}c^{n}[/itex] | n [itex]\geq[/itex] 0} [itex]\subset[/itex] L

    If I show that T is not context free, does that show that L is not context free?
  2. jcsd
  3. Mar 9, 2012 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    The language of all strings is context-free (even regular), right? ....
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook