# Context free grammar for $L = \{w \text{ | }w \in \{a,b\}^*, |w|_a=|w|_b-1\}$

I'm trying to find a grammar for $$L = \{w \text{ | }w \in \{a,b\}^*, |w|_a=|w|_b-1\}$$, which is proving to be tricky.

I know that $$L_2 = \{w \text{ | }w \in \{a,b\}^*, |w|_a=|w|_b\}$$ has the following one, so I have been trying to modify it so that I "force" to have one more $$b$$, but I don't see how to do this. The obvious choice would be to replace $$\epsilon$$ with $$b$$, but that would potentially get two more $$b$$'s. Is there a trick for this one?

\begin{align} S &\to \epsilon \\ S &\to aSbS \\ S &\to bSaS \enspace. \end{align}

You asked for a trick. Yes, there is a construction to add a single letter to the strings in the language of a grammar given in advance.

For simplicity I will start with a grammar in Chomsky Normalform, i.e., every rule is of the form $$A\to BC$$ or $$A\to \sigma$$, with $$A,B,C$$ variables and $$\sigma$$ terminal.

Assume there is a context-free grammar $$G$$ for a language $$L$$ then we can construct a grammar for "strings in $$L$$ with an extra $$b$$" in a generic way. We use the variables to hand down the instruction "add a $$b$$" to one of their successors. For each variable $$A$$ we introduce a copy $$A_1$$ that carries this task.

Thus, for every rule $$A\to BC$$ we add the new rules $$A_1\to B_1C$$ and $$A_1\to BC_1$$. Morever, we make it possible to add the extra $$b$$, with rules $$A_1 \to bA$$. Now starting with $$S_1$$ derivations are as before, except at some point in the derivation a single $$b$$ is introduced. Note that we need to generate a $$b$$ since variables $$A_1$$ cannot be rewritten into terminals. One tiny detail: the $$b$$ can only be introduced before a variable, so in order to append a $$b$$ we need the additional rule $$S_1\to Sb$$. (We need no other additional rules since a $$b$$ after a variable can be replaced by a $$b$$ before another variable, except at the end.)

• @Lightsong, this answer, simple and powerful, should be the accepted answer. – John L. Jan 29 at 0:33
• Wow, that's really clever. Thank you! As @JohnL. said, I will be marking this one as accepted. – Lightsong Jan 29 at 8:23

You can simply consider the following grammar: $$S\to S_1 b S_1$$ where $$S_1$$ is the start variable of a grammar for the language of words $$w$$ with $$|w|_a = |w|_b$$. Correctness is self-explanatory.

So using the grammar you wrote, you get the following grammar: $$S\to T b T$$

$$T \to aTbT| bTaT | \epsilon$$

• I see, that was...simple. Thank you! Going with that construction, I guess $$S\to S_1 b S_1 b S_1$$ would for example give $L = \{w \text{ | }w \in \{a,b\}^*, |w|_a=|w|_b-2\}$, right? – Lightsong Jan 28 at 15:24
• Yes. It should be easy to prove. Clearly, every generated word is in the language. Also, every word in the language has at least two b's: pick two b's and generate everything in between, before, and after them using $S_1$ – Bader Abu Radi Jan 28 at 15:35
• great, thank you :) – Lightsong Jan 28 at 15:49
• @BaderAbuRadi Although I believe the grammar for two extra $b$'s in the comments is correct, I do not think it is as simple as "pick two b's and generate everything in between". Note that the two $b$'s have to be chosen such that the between, before and after parts have an equal numbers of $a$'s and $b$'s. – Hendrik Jan Jan 28 at 21:41
• You're right. I missed that. – Bader Abu Radi Jan 29 at 6:27