[Math] Proving a set is language generated by given grammar

automatacomputer sciencecontext-free-grammarsolution-verification

I have grammar $G$ with productions $S\rightarrow aS|aSbS|\epsilon$, and task is to prove that $L(G)=\{w|$every prefix of $w$ has at least $a$'s as $b$'s$\}$ (I'm not sure if translation is correct, I apologize =D)

I'm trying to prove inclusion, lets say given set is $A$, $A \subseteq L(G)$ using induction for length of word $w \in A$.

I have basis for length $0,1$ and supose it's true for words with length less and equal $n$.

Step:let $w \in A$ and $|w|=n+1$. Since first letter of the word is also prefix then first letter must be $a$, $w=aw_1$. Length $|w_1|=n$ and by assumption $w_1 \in L(G)$, so there is derivation $S \rightarrow^*w_1$ . And now using production of grammar $G$ we have, $S \rightarrow aS \rightarrow^*aw_1=w$ which implies $w \in L(G)$.

I'm not sure if my proof is correct since I didn't used second production anywhere (it is used in other inclusion, but not here). I would be grateful if you could check this and tell if there's mistake.

Best Answer

I think your solution is incomplete, how do you know that $w_1$ is in $L(G)$. Consider $w=aaabbb$,then $w1=aabbb$ which clearly is not in the language.

I will put my answer below, if you want to think more on it you can stop here.


Now on, by the property I mean :"every prefix of $w$ has at least as much $a$s as $b$s".

The proof must consist of two parts: 1:proving every string produced by the grammar has the aforementioned property, 2:proving every string with the property is produced by the grammar. This is the way I would prove it.

For part one, suppose the property holds for all strings produced by the grammar like $u$ where $|u|<n$. Now suppose $|w|=n>0$, then the first production in derivation of $w$ must be $S\to aS$ or $S\to aSbS$. In either case $S$ symbols will be replaced with strings in $L(G)$ with length less than $n$, and we know in such strings the property holds. Then it is easy to show that it must also hold in $w$.

For part two, suppose every string with the property with length less than $n$ is produced by the grammar, suppose $w$ with length $n>0$ has the property. Then $w=av,|v|<n$, now if $v$ also has the property then $w$ can be made with a sequence of derivations starting with $S\to aS$. If $v$ does not have the property then $v$ must have at least one $b$, consider the last $b$ from left to right in $w$,then $w=axby$. Note that the $b$ is the last $b$ and $y$ can be $\epsilon$. Since $w$ has the property, then $axb$ has the property, then $x$ hast the property and $|x|<n$. Also, as there are no $b$s in $y$, then it has the property too, so $w$ can be made with a sequence of derivations starting with $S\to aSbS$, the first $S$ makes $x$ and the second one makes $y$.

P.S: You should add base case for the inductions, I didn't mention them.