Results 1 to 2 of 2

Math Help - Context free language question.

  1. #1
    Junior Member
    Joined
    Dec 2008
    Posts
    28

    Context free language question.

    Let E = {a^i b^j | i != j and 2i != j}. Show that E is a context-free language.

    I'm having trouble where to begin making the grammar. Could anyone give me a push in the right direction?
    Thank you.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,559
    Thanks
    785
    Note that i != j and 2i != j is equivalent to 2i < j or j < 2i < 2j or i > j. The trickiest part is to generate {a^i b^j | j < 2i < 2j}. Let R(i, j) be j < 2i < 2j. I have a hypothesis, which I have not fully checked, that R can be defined inductively as follows.

    (1) For all k > 1, (k, 2k - 1) is in R.
    (2) For all i, j, if (i, j) is in R, then (i + 1, j + 1) is in R.

    In turn, the relation S(i, j) <=> i > 1 and j = 2i -1 can be inductively generated like this.

    (1) (2, 3) is in S.
    (2) For all i, j, if (i, j) is in S, then (i + 1, j + 2) is in S.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Context free grammar question.
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 25th 2011, 05:09 PM
  2. context-free grammar
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: March 27th 2011, 12:51 PM
  3. please help, context free language
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: December 6th 2010, 09:27 AM
  4. context-free language and grammar
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: June 28th 2010, 05:42 PM
  5. context-free grammar
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 6th 2010, 10:26 PM

Search Tags


/mathhelpforum @mathhelpforum