For language $L = \{ x \in \{a,b\}^* \mid \#_a x = \#_b x \}$, I came up with the following CFG: $$S \rightarrow aSbS \mid bSaS \mid \varepsilon.$$ It can be easily shown that it is correct (quick example, for string $x = aabb$ we have these derivations: $S \rightarrow aSbS \rightarrow^* aaSbSb\varepsilon \rightarrow^* aa\varepsilon b \varepsilon b \rightarrow aabb$). Then I was asked to provide a mathematical proof, which is more like to be intended as a formalism, to prove, indeed, the correctness of such CFG.

Arguably, by induction, one could assume it holds that $\forall k\leq n$, $|x| = 2k$ and then test a string $x$ with number of characters $|x| = 2n + 2$. So string $x$ is in the form of $x = au'bu''$. But now how can I show that $u'$ and $u''$ still contain an equal number of $a$'s and $b$'s? Sorry if I'm missing something and might be easier than I think.


There are two implications involved in the correctness. Every string in $L$ can be derived by the CFG (completeness) and every string derived by the grammar belongs to $L$ (consistency). I think you want an argument to formalize the first implication by induction.

Assuming the string $x\in L$ starts with an $a$, there must be a position with letter $b$ such that the string is of the form $aubv$ such that the $\#_a(u)=\#_b(u)$. The argument I know is by counting. Read the letters in $x$ one by one, and add $1$ for each $a$, subtract $1$ for each $b$. As the number of $a$'s equals the number of $b$'s, the count starts and stops with $0$. The counts becomes $1$ after the first letter, and must drop back to $0$ at some position with a $b$. In between we have seen an equal number of $a$'s and $b$'s.

Now that $x=aubv$ with $x\in L$ and $u\in L$ it is easy to argue that also $v\in L$.

| cite | improve this answer | |
  • $\begingroup$ Good reasoning, and as regards the consistency property, i.e. $ L(G) \subseteq L $, it is basically already proved because, being $S \rightarrow aSbS \mid bSaS $, we can reach $ x = aubu$ or $ x = buau$ at a certain point, and $x \in L$, right? $\endgroup$ – Antonio Frighetto Oct 26 '18 at 11:37
  • $\begingroup$ @Antonio Indeed, $L(G)\subseteq L$ is easy by design of the grammar. If $S\Rightarrow^* u$ and $S\Rightarrow^* v$ assuming $u,v\in L$, then also $aubv, buav\in L$. Induction on the length of the derivation, or depth of the derivation tree. $\endgroup$ – Hendrik Jan Oct 26 '18 at 14:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.