Results 1 to 13 of 13

Math Help - Grammar problem

  1. #1
    Super Member
    Joined
    Jun 2008
    Posts
    829

    Grammar problem

    Given the grammar G=({S},{a,b},P,S) where:
    S -> SS | aSa | bSb | E

    E is empty

    What is the language generated ?
    is (a+b)^* ?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Apprentice123 View Post
    Given the grammar G=({S},{a,b},P,S) where:
    S -> SS | aSa | bSb | E

    E is empty

    What is the language generated ?
    is (a+b)^* ?
    I believe the language generated is equivalent to this, except that () is replaced by aa and [] by bb.

    By the way, I don't know what you meant by (a+b)^* because I think the "+" operator is only defined when it is a superscript, as in a^+, meaning aa^*.
    Last edited by undefined; June 28th 2010 at 11:38 AM. Reason: typo
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Jun 2008
    Posts
    829
    OK. A derivation would:
    SS
    aSabSb
    abSbabaSab
    abEbabaEab
    abbabaab

    What language is that?

    a^n b^n with n>=0 ?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Apprentice123 View Post
    OK. A derivation would:
    SS
    aSabSb
    abSbabaSab
    abEbabaEab
    abbabaab

    What language is that?
    Compare what you just wrote with

    SS
    (S)[S]
    ([S])[(S)]
    ([])[()]

    By the way it's not typical to write E inside the expression.

    Quote Originally Posted by Apprentice123 View Post
    a^n b^n with n>=0 ?
    No, because you just produced a string that is not in that language. The language a^n b^n with n>=0 has strings like

    E
    ab
    aabb
    aaabbb

    etc.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Jun 2008
    Posts
    829
    I think the language is: number pair of a's and b's (considering 0 as pair). Is that it?
    How do I know if this grammar is ambiguous?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Apprentice123 View Post
    I think the language is: number pair of a's and b's (considering 0 as pair). Is that it?
    How do I know if this grammar is ambiguous?
    Well you'd have to mention "nested" in there somewhere, and perhaps "matching."

    To tell the truth, I'm not sure of the best way to define the context-free language in English or in symbols. I would probably end up taking the "easy way out" by describing the language as: the language obtained by taking the language that contains all strings consisting of two different kinds of matching nested parentheses () and [], and replacing ( with a and ) with a and [ with b and ] with b.

    There's probably a better way to say this. But if it were a homework assignment, I would think of the easy way out as "good enough" and wait for the professor's/grader's feedback.. that's just me.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member
    Joined
    Jun 2008
    Posts
    829
    Thanks. How do I know if this grammar is ambiguous?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Apprentice123 View Post
    Thanks. How do I know if this grammar is ambiguous?
    Definition of ambiguous grammar: there exists a string that can be generated by the grammar in more than one way.

    I think we can use trivial examples here

    S -> E

    S -> SS -> E

    Or slightly less trivial

    S -> SS -> aSaaSa -> aaaa

    S -> aSa -> aaSaa -> aaaa

    (So the grammar is in fact ambiguous.)
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Super Member
    Joined
    Jun 2008
    Posts
    829
    Thanks
    The tree derivation of the word aabbaaaa is:

    Code:
                   S
                /  |  \
              a    S     a  
                 /    \
               S       S
            /  | \    / | \
          a   S  a  a  S a
            /  | \        |
          b   S  b      E
               |
               E
    ???
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Apprentice123 View Post
    Thanks
    The tree derivation of the word aabbaaaa is:

    Code:
                   S
                /  |  \
              a    S     a  
                 /    \
               S       S
            /  | \    / | \
          a   S  a  a  S a
            /  | \        |
          b   S  b      E
               |
               E
    ???
    Looks good to me. Keep in mind that this is not the only possible way to generate the string.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Super Member
    Joined
    Jun 2008
    Posts
    829
    Thanks
    What would a derivation more right and more left ?
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Apprentice123 View Post
    Thanks
    What would a derivation more right and more left ?
    More right and more left? You mean the with the balance of the tree shifted, so to speak? Just play around, you'll find something.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Super Member
    Joined
    Jun 2008
    Posts
    829
    Thank you
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. context-free grammar
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: March 27th 2011, 12:51 PM
  2. Simplification grammar
    Posted in the Discrete Math Forum
    Replies: 17
    Last Post: June 30th 2010, 06:16 AM
  3. Context-free grammar
    Posted in the Discrete Math Forum
    Replies: 16
    Last Post: June 29th 2010, 10:41 AM
  4. Regular Grammar
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: June 20th 2010, 09:58 AM
  5. context-free grammar
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 6th 2010, 10:26 PM

Search Tags


/mathhelpforum @mathhelpforum