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

1. ## 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.

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

Originally Posted by LostProjectile
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?

Originally Posted by LostProjectile
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.

3. ## 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.

4. ## 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.

Originally Posted by LostProjectile
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".

Originally Posted by LostProjectile
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.

5. ## 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.

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

Originally Posted by LostProjectile
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.