Results 1 to 6 of 6

Math Help - Proving strings generated by a grammar can be decomposed in a certain way

  1. #1
    Newbie
    Joined
    Sep 2011
    Posts
    17

    Proving strings generated by a grammar can be decomposed in a certain way

    If I have a grammar

    S -> aSbS|epsilon

    With the language it generates represented by L and I want to prove that for all strings w = L - {epsilon}, w can be decomposed to w = a u b v where u and v exist in L, does the following proof make sense?

    If w has the same number of a's and b's, then there is a certain b in the string w where the number's of a's and b's at that point match. Then w can be generated by the production rule S->aSbS where the first S then can be used to derive u and the second S can be used to drive v.

    Is my proof okay? Am I proving enough or can I make this more concrete? Any suggestions would be appreciated.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,517
    Thanks
    769

    Re: Proving strings generated by a grammar can be decomposed in a certain way

    Quote Originally Posted by LostProjectile View Post
    If w has the same number of a's and b's
    I don't think this premise is necessary. Are you talking about any string at all with the same number of a's and b's? Why should it belong to the language?

    Quote Originally Posted by LostProjectile View Post
    then there is a certain b in the string w where the number's of a's and b's at that point match.
    I am not sure what it means for the number's of a's and b's to match at that point. Are you talking about the number's of a's and b's before that point?

    I think all one needs is to consider the first application of the rule in the derivation of w. Then trace where the a and b that appear in that first aSbS end up in the final word. This will give the required partition.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Sep 2011
    Posts
    17

    Re: Proving strings generated by a grammar can be decomposed in a certain way

    Sorry, I wasn't talking about any string with the same number of a's and b's, only those derived from that grammar.

    For the part where I'm saying the number of a's and b's match at that point, I'm saying that if you minus the number of b's from the number of a's as you go, that's the point where you are at 0. I found that denotes the exact b from aSbS from the first application of the rule to show the partitions.

    I'm just having trouble formalizing this idea into my proof. Since now I guess I could say u and v must also exist in L since they are also derived from S. Thank you for your reply.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,517
    Thanks
    769

    Re: Proving strings generated by a grammar can be decomposed in a certain way

    Let me denote the number of a's in w by #a(w), and similarly for b's.

    Quote Originally Posted by LostProjectile View Post
    Sorry, I wasn't talking about any string with the same number of a's and b's, only those derived from that grammar.
    For every w ∈ L, #a(w) = #b(w) (easy to show by induction), so perhaps instead of "If w has the same number of a's and b's" it should say "Since w has the same number of a's and b's".

    Quote Originally Posted by LostProjectile View Post
    For the part where I'm saying the number of a's and b's match at that point, I'm saying that if you minus the number of b's from the number of a's as you go, that's the point where you are at 0. I found that denotes the exact b from aSbS from the first application of the rule to show the partitions.
    Well, every w ∈ L ends with b, and since #a(w) = #b(w), the last b is a point where the number's of a's and b's match. Perhaps there are several such points. Are you talking about the first one? Also, it is not immediately clear to me why this b is the image of b in the first aSbS of the derivation.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Sep 2011
    Posts
    17

    Re: Proving strings generated by a grammar can be decomposed in a certain way

    For your last question, I am referring to the first occurrence of when the #a(w) = #b(w). I found by writing out strings from this grammar, this is always the case to find the b from the first application of the rule and I though this could help me to show where the partition lies to denote the substrings u and v.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,517
    Thanks
    769

    Re: Proving strings generated by a grammar can be decomposed in a certain way

    Quote Originally Posted by LostProjectile View Post
    I am referring to the first occurrence of when the #a(w) = #b(w). I found by writing out strings from this grammar, this is always the case to find the b from the first application of the rule and I though this could help me to show where the partition lies to denote the substrings u and v.
    I think you are right. When you start with aSbS and it turns into a u b v (keeping the same occurrence of b), #a(u) = #b(u), so #a(a u) = #b(a u) + 1 and #a(a u b) = #b(a u b). One must make sure, though, that the matching point can't happen earlier. But I still think that it is easier to consider the first aSbS in the derivation.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: October 30th 2010, 11:25 AM
  2. Simplification grammar
    Posted in the Discrete Math Forum
    Replies: 17
    Last Post: June 30th 2010, 05:16 AM
  3. Grammar problem
    Posted in the Discrete Math Forum
    Replies: 12
    Last Post: June 29th 2010, 05:42 AM
  4. Regular Grammar
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: June 20th 2010, 08:58 AM
  5. Replies: 5
    Last Post: May 31st 2009, 09:30 AM

Search Tags


/mathhelpforum @mathhelpforum