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).


1 Answer 1


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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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