# CFG for $L=\{ \omega \in \{ a,b,c,d \}^* : |\omega|_a = |\omega|_b \}$

Given the language:

$$L=\{ \omega \in \{ a,b,c,d \}^* : |\omega|_a = |\omega|_b \}$$

I propose the following grammar: \begin{align*} S &\to \varepsilon \mid aSbS \mid bSaS \\ S &\to cS \mid dS \mid Sc \mid Sd \end{align*}

I want to know if this is correct or if there exists a smarter grammar (a shorter grammar).

I'm going to address the second part of the question first, about a "smarter grammar." One improvement that can be made is omitting the rules

$$S \rightarrow Sc \hspace{10px}| \hspace{10px} Sd.$$

Assuming we have made that change, to answer the first part, if the grammar is correct we need to answer two questions.

1. Does $$S$$ only generate strings within $$L$$?
2. Can every string in $$L$$ be generated by $$S$$?

If the answer to these questions is both yes, then a string is in $$L$$ if and only if it is generated by $$S$$, which means that $$S$$ is a correct grammar for the language.

The answer to 1. is clearly yes because every string generated by $$S$$ must have the same number of $$a$$'s as it does $$b$$'s because in every rule where an $$a$$ is present a $$b$$ is also present, and vise versa.

The answer to number 2 is a bit trickier. We will use induction on $$|\omega|_a = |\omega|_b$$ to show that any string in $$L$$ can be generated by $$S$$

(Base case $$n=0$$) If $$|\omega|_a = |\omega|_b = 0$$, then $$\omega$$ consists of a sequence of $$c$$'s and $$d$$'s, and can be generated by scanning over it using the rules

$$S \rightarrow cS \hspace{10px} | \hspace{10px} dS$$

until we terminate with $$S \rightarrow \epsilon$$.

($$n$$ implies $$n+1$$) Assume by induction that for all $$\omega \in L$$ with $$|\omega|_a = |\omega|_b \leq n$$ that $$\omega$$ can be generated by $$S$$. Now let $$\omega' \in L$$ be such that $$|\omega'|_a = |\omega'|_b = n+1$$.

At some point in $$\omega'$$ there must be at least one time that an $$a$$ comes before a $$b$$ (with only $$c$$'s and $$d$$'s between them) or a $$b$$ comes before an $$a$$ (with only $$c$$'s and $$d$$'s between them). Without loss of generality, we can assume there is an $$a$$ that comes before a $$b$$.

Now, we can decompose $$\omega' = XaYbZ$$ where $$|X|_a + |Z|_a = |XZ|_a = n$$ (and the same for $$b$$) and $$Y \in \{c,d\}^*$$ . This holds because we are taking one $$a$$ and one $$b$$ from $$\omega'$$ which had $$n+1$$ of each which leaves $$n$$ in the rest of the string, and we know that there is a pair of $$a$$ and $$b$$ with just $$c$$ and $$d$$ between.

Now we can get a little clever and observe that the string $$XcZ \in L$$ and $$|XcZ|_a = |XcZ|_b = n$$ and therefore, by the inductive hypothesis, $$XcZ$$ can be generated by $$S$$.

Now here's the tricky part. Consider the process that generated $$XcZ$$. At some point in the generation, we must have used the rule $$S \rightarrow cS$$ to generate the $$c$$ between $$X$$ and $$Z$$. If we instead chose to use

$$S \rightarrow aS^*bS$$

as the expansion where $$S^*$$ generates $$Y$$ as in the case where $$n = 0$$, and did everything else exactly the same, then what happens is we replace the $$c$$ in $$XcZ$$ with $$aYb$$, and get the string $$XaYbZ$$. This demonstrates that $$\omega'$$ can be generated by $$L$$ because we have just found a process by which it can be generated by $$S$$.

Therefore by induction on $$|\omega|_a = |\omega|_b$$ every string in $$L$$ can be generated by $$S$$.