Results 1 to 2 of 2

Math Help - Need to practice CFG

  1. #1
    Junior Member
    Joined
    Nov 2008
    Posts
    36

    Need to practice CFG

    I'm trying to practice for my exams, and the one problem I'm having is creating context grammars for a specific set. I am not sure how to go about creating context grammar, except for the trivial case. Here are some cfg's that I have been practicing on, can you check for correctness, thanks.

    S1 = { a^xb^y}

    1)  x = y  : S->aSb | \epsilon
    2)  x > y  : S->aSB | aS | a
    3)  x = 2y: S->aaSy | \epsilon


    S2 = { a^xb^ya^z} for z = x + y

    This one I wasn't sure. This is what I got so far from reduction :

    //Substituting x+y for z I got :
    S2 = { a^xb^ya^xa^y}

    Now I'm not sure where to got with this. A similar problem also exist for condition z = x-y

    Any hints and not the answer directly would be very appreciated. Thank you.

    EDIT:

    So for S2 here is what I got :

    S2 = { a^xb^ya^xa^y}

    For the case y>=x we can express y as y = x + n, n>= 0

    Thus we can decompose S2 into:

    S2 = { a^xb^ya^xa^y}
    S2 = { a^xb^nb^xa^xa^na^x}

    Thus for the above S2 we can now easily make a CFG as so:

    Q -> U | null
    U -> aUa| T
    T -> nTa| S
    S -> bSa | null


    we can apply similar process for j<=x, and I got:

    A -> B | null
    B -> aBa | C
    C -> aCa | D
    D -> bDa | null

    Thus a grammar that accepts S2 is G ->Q|A

    Is that correct?
    Last edited by Matter_Math; October 24th 2010 at 08:25 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Nov 2008
    Posts
    36
    Sorry for the bump, I just was hoping someone can check my work.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. practice
    Posted in the LaTeX Help Forum
    Replies: 3
    Last Post: December 14th 2011, 10:33 PM
  2. AP practice question
    Posted in the Calculus Forum
    Replies: 2
    Last Post: June 1st 2010, 12:34 PM
  3. SAT Practice Exam
    Posted in the Math Software Forum
    Replies: 0
    Last Post: January 8th 2010, 03:14 PM
  4. Practice
    Posted in the LaTeX Help Forum
    Replies: 2
    Last Post: July 20th 2009, 12:16 AM
  5. Sat Practice Help
    Posted in the Trigonometry Forum
    Replies: 2
    Last Post: January 28th 2007, 08:50 AM

Search Tags


/mathhelpforum @mathhelpforum