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 &quot;force&quot; 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 &amp;\to \epsilon \\
  S &amp;\to aSbS \\
  S &amp;\to bSaS \enspace.
\end{align}$$
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$$