Results 1 to 14 of 14

Thread: More Grammar Problems

  1. #1
    Junior Member
    Joined
    Jun 2017
    From
    San Diego
    Posts
    25
    Thanks
    1

    Question More Grammar Problems

    Here are some grammar problems that I can't seem to wrap my brain around. I've already solved them but I want to see what you guys think:

    5. (2 points) Write a grammar that describes the following language:
    L = {ab, ac, ad}


    6. (2 points) consider the following grammar:
    S X Y X x
    Y Y y
    Y y


    This grammar describes a language (i.e. a set of strings). Describe (in simple English) the set of strings that this grammar describes.
    7. (3 points) Optional extra credit question: Given the alphabet {a, b} write a grammar for the following language:
    The language that has/accepts all strings that start with an a

    8. (3 points) Optional extra credit question 2: What language does the following grammar define? Describe it in simple English.
    S aZ b Z aZ b Z ab
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Jun 2017
    From
    San Diego
    Posts
    25
    Thanks
    1

    Re: More Grammar Problems

    Here are the answers that I already have:

    5.

    1. S → A
    2. A→ ac
    3. B → ad
    4. C → ab

    6.
    1. The S is replaced with XY (by rule 1). So then we’re left with XY.
    2. The X in XY turns into x by rule 2.
    3. The Y in XY becomes Yy by rule 3.
    4. The Y in Yy is replaced with y by rule 4 which leaves us with yy. So now we have xyy

    7.

    1. S → AB
    2. A→ Aa
    3. A → a
    4. B → b
    5. B → ab

    8.
    1. The S is replaced with aZb (by rule 1) which leaves us with aZb.
    2. The Z in aZb is replaced with aZb by rule 2. This leaves us with aZb.
    3. The Z in aZb is replaced with ab (by rule 3). This leaves us with aabb.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Nov 2010
    Posts
    2,530
    Thanks
    961

    Re: More Grammar Problems

    5 will never generate B or C. I'd try:
    $S\to AB$
    $A\to a$
    $B\to b$
    $B\to c$
    $B\to d$

    6. By the rules you have shown in other problems, I do not believe they are activated in order.
    S becomes XY is true. X becomes x is true, but I believe either Y becomes Yy OR Y becomes y. This would mean that you can get xy, xyy, xyyy, etc. It is x followed by a finite number of y's (I say finite because most languages require strings to be finite)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Nov 2010
    Posts
    2,530
    Thanks
    961

    Re: More Grammar Problems

    7 is also wrong. You cannot get the following string: abaa.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Nov 2010
    Posts
    2,530
    Thanks
    961

    Re: More Grammar Problems

    8 again seems to imply an or, not a strict adherence to the order in which the rules were listed. You can wind up with a string of a's concatenated with an equally sized string of b's where you have at least 2 of each.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Jun 2017
    From
    San Diego
    Posts
    25
    Thanks
    1

    Re: More Grammar Problems

    I re-did #7 and this is what I got. The only thing I am certain is that this is for grammar-free problems. Nevertheless I gave a second shot.

    1. S → AB
    2. A→ Aa
    3. A → a
    4. B → b
    5. B → ab
    6. B → ε
    7. A → ε
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Nov 2010
    Posts
    2,530
    Thanks
    961

    Re: More Grammar Problems

    What does $\varepsilon$ mean? Is that the null string?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member
    Joined
    Jun 2017
    From
    San Diego
    Posts
    25
    Thanks
    1

    Re: More Grammar Problems

    Yes. It means it's emty.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Joined
    Nov 2010
    Posts
    2,530
    Thanks
    961

    Re: More Grammar Problems

    Then, how about this:

    $S \to AB$
    $A \to a$
    $B \to aB$
    $B \to bB$
    $B \to \varepsilon$

    Now, it starts with an a. The next character could be a or b or nothing, followed by a or b or nothing, followed by a or b or nothing...
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Junior Member
    Joined
    Jun 2017
    From
    San Diego
    Posts
    25
    Thanks
    1

    Re: More Grammar Problems

    Doesn't b need to be alone at some point? Or does that violate the language ("The language that has/accepts all strings that start with an a”) given?
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor
    Joined
    Nov 2010
    Posts
    2,530
    Thanks
    961

    Re: More Grammar Problems

    Quote Originally Posted by marsandfruit View Post
    Doesn't b need to be alone at some point? Or does that violate the language ("The language that has/accepts all strings that start with an a”) given?
    I don't believe that is necessary. You could have $b$ alone if you want to. But, essentially, what my rules state is that it must begin with an a. Then, it has three choices. It can add an $a$ + keep going, it can add a $b$ + keep going, or it can stop. So, after the first pass, it will be one of these:
    aaB
    abB
    a

    If it goes for two passes, here are the six choices:
    aaaB
    aabB
    aa
    abaB
    abbB
    ab

    If it goes for three passes, it would be one of these twelve:
    aaaaB
    aaabB
    aaa
    aabaB
    aabbB
    aab
    abaaB
    ababB
    aba
    abbaB
    abbbB
    abb

    You see how each step, it adds another character and keeps going or it stops?
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Junior Member
    Joined
    Jun 2017
    From
    San Diego
    Posts
    25
    Thanks
    1

    Re: More Grammar Problems

    Quote Originally Posted by marsandfruit View Post
    Doesn't b need to be alone at some point? Or does that violate the language ("The language that has/accepts all strings that start with an a”) given?
    Nevermind. I understand why now. Sorry I'm just learning this stuff and I want to make sure it's correct.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Junior Member
    Joined
    Jun 2017
    From
    San Diego
    Posts
    25
    Thanks
    1

    Re: More Grammar Problems

    Yes I do! Thank you so much!

    And for #8 would there be a similar statement to define the language? Would be "Anything after a is included in this language."
    Last edited by marsandfruit; Jun 23rd 2017 at 12:55 PM.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    MHF Contributor
    Joined
    Nov 2010
    Posts
    2,530
    Thanks
    961

    Re: More Grammar Problems

    You can wind up with:
    aabb
    aaabbb
    aaaabbbb
    aaaaabbbbb

    It is a number of a's (at least two) followed by an equal number of b's

    This is certainly not anything after a.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Induction and Grammar
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Mar 29th 2014, 07:28 AM
  2. Simplification grammar
    Posted in the Discrete Math Forum
    Replies: 17
    Last Post: Jun 30th 2010, 05:16 AM
  3. Grammar problem
    Posted in the Discrete Math Forum
    Replies: 12
    Last Post: Jun 29th 2010, 05:42 AM
  4. Regular Grammar
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Jun 20th 2010, 08:58 AM
  5. context-free grammar
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 6th 2010, 09:26 PM

Search Tags


/mathhelpforum @mathhelpforum