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

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    The language of all strings is context-free (even regular), right? ....
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Context Free Languages, Pumping Lemma
  1. Troubling Lemma (Replies: 6)

  2. Diagonal Lemma (Replies: 0)

Loading...