Page 1 of 2 12 LastLast
Results 1 to 15 of 17

Math Help - Context-free grammar

  1. #1
    Super Member
    Joined
    Jun 2008
    Posts
    829

    Context-free grammar

    Develop context-free grammars that generate languages:

    L1 = {w|w is palindrome in {a,b}^* , w=w^*}
    L2 = {ww^* | w is word of {a,b}^*}


    My attempt
    1)
    S -> aSa | bSb | E | a | b
    E is empty
    Correct ?

    2) I could not. Any tips?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Jun 2008
    Posts
    829
    2) I think is (ww)^* which means that it is a word that read from the early to mid is the same when read to the end of the half. But I can not generate the language
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Apprentice123 View Post
    Develop context-free grammars that generate languages:

    L1 = {w|w is palindrome in {a,b}^* , w=w^*}
    L2 = {ww^* | w is word of {a,b}^*}


    My attempt
    1)
    S -> aSa | bSb | E | a | b
    E is empty
    Correct ?

    2) I could not. Any tips?
    1) The syntax of L1 = {w|w is palindrome in {a,b}^* , w=w^*} does not seem right. How can w = w^*? My guess is that one of the following is meant:

    (1a) L1 = {w|w is palindrome in {a,b}^*}

    Then I think your answer would be correct except that empty strings are not considered palindromes. So I would modify as follows:

    S -> aSa | bSb | a | b

    (1b) L1 = {w|u is palindrome in {a,b}^* , w=u^*}

    Consider that every single character is a palindrome, for example "a" is a palindrome, and so is "b." So this is just all strings over {a,b}^*.

    S -> Sa | Sb | E

    (1c) L1 = {w*|w is palindrome in {a,b}^*}

    This is equivalent to (1b).

    2) With similar reasoning to above, I believe this language is all non-empty strings over {a,b}^*. So I get

    S -> Sa | Sb | a | b
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Jun 2008
    Posts
    829
    OK. Thank you
    And the language:

    L3 = {w | w regular expression is about {x} }

    Which means: it is about regular expression {x} ? I can generation a context-free grammar ?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Apprentice123 View Post
    OK. Thank you
    And the language:

    L3 = {w | w regular expression is about {x} }

    Which means: it is about regular expression {x} ? I can generation a context-free grammar ?
    I'm not sure exactly what this means, but I guess it means regular expressions with an alphabet consisting of the single character x, such as x? , x* , x+ , x | x, etc. There isn't a whole lot of variety, and the most general regex is x*. So I would just write

    S -> Sx | E

    Maybe check with your book or notes to see if there is some other definition given though.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Jun 2008
    Posts
    829
    Thanks. I think you're right
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member
    Joined
    Jun 2008
    Posts
    829
    I found another language I do not understand

    L4 = {w|w is word of {x,y,(,)}^* with balanced parentheses}

    What "with balanced parentheses" ?
    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
    I found another language I do not understand

    L4 = {w|w is word of {x,y,(,)}^* with balanced parentheses}

    What "with balanced parentheses" ?
    () balanced
    (()) balanced
    ()() balanced
    (()()) balanced
    (() not balanced
    )( not balanced
    (())) not balanced

    potentially useful link.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Super Member
    Joined
    Jun 2008
    Posts
    829
    Then it is just that:

    S -> x | y | () | (S) | E

    Correct ?
    Last edited by Apprentice123; June 29th 2010 at 08:40 AM.
    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
    Then it is just that:

    S -> x | y | () | (S) | E

    Correct ?
    This isn't correct because for example there is no way to get the string

    x()
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Super Member
    Joined
    Jun 2008
    Posts
    829
    S -> xS | yS | ()S | (S) | E


    I had not noticed. Now I think that is correct. This right?
    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
    S -> xS | yS | ()S | (S) | E


    I had not noticed. Now I think that is correct. This right?
    Hmmm how would you produce (())(()) ?
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Super Member
    Joined
    Jun 2008
    Posts
    829
    Now I can
    S -> xS | yS | ()S | (S) | SS | E

    ???
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Super Member
    Joined
    Jun 2008
    Posts
    829
    Now I can
    S -> xS | yS | ()S | (S) | SS | E

    ???
    Follow Math Help Forum on Facebook and Google+

  15. #15
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Apprentice123 View Post
    Now I can
    S -> xS | yS | ()S | (S) | SS | E

    ???
    I believe this is right; however, S -> ()S is unnecessary since you can always do

    S => SS => (S)S => ()S

    using just the other rules. So we have

    S -> xS | yS | (S) | SS | E
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Proof Please: Context Free Grammar
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 28th 2011, 08:10 PM
  2. Context free grammar question.
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 25th 2011, 05:09 PM
  3. context-free grammar
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: March 27th 2011, 12:51 PM
  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