As an exercise we were supposed to find a grammar $G$ that generates language $L(G) = \{w \in \{a,b\}^* \mid  |w|_a = |w|_b\}$.That was not so hard, I found a grammar which I think is correct:$S \longrightarrow bA \mid aB$$A \longrightarrow a \mid aS \mid bAA$$B \longrightarrow b \mid bS \mid aBB$Though then I found out that this grammar is ambiguous.So the question is, is there any context free grammar generating language $L$ that is not ambiguous? I've read that there is no algorithm to determine whether a grammar is ambiguous. So if there is such grammar, how can we prove it is? Or is there any way to transform my grammar $G$ to become unambiguous?
Finding a unambiguous grammar
context free;formal grammars;ambiguity
You can get an unambiguous grammar by thinking of words in $L$ as walks that start and end on the Y axis; each $a$ corresponds to a move $\nearrow$, and each $b$ corresponds to a move $\searrow$. Each such walk can be decomposed into segments of the form $\nearrow \cdots \searrow$ and $\searrow \cdots \nearrow$ which only touch the Y axis at the endpoints. Moreover, this decomposition is unique.In turn, in a walk of the form $\nearrow \cdots \searrow$, the $\cdots$ part is itself a concatenation of walks of the same form, and this decomposition is unique. Alternatively, if you convert $\nearrow \mapsto ($ and $\searrow \mapsto )$, then walks of the form $\nearrow \cdots \searrow$  become valid strings of balanced parenthesis, surrounded by a pair $()$.Putting everything together, we get the following unambiguous grammar:$$\begin{align*}&S \to AS \mid BS \mid \epsilon \\&A \to a X b \\&X \to AX \mid \epsilon \\&B \to b Y a \\&Y \to BY \mid \epsilon \end{align*}$$Actually proving that this grammar generates $L$ and that it is unambiguous is tedious, and left to you.