3
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

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

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

$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$ – Lightsong Jan 28 at 15:24
  • $\begingroup$ 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$ $\endgroup$ – Bader Abu Radi Jan 28 at 15:35
  • $\begingroup$ great, thank you :) $\endgroup$ – Lightsong Jan 28 at 15:49
  • 1
    $\begingroup$ @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. $\endgroup$ – Hendrik Jan Jan 28 at 21:41
  • $\begingroup$ You're right. I missed that. $\endgroup$ – Bader Abu Radi Jan 29 at 6:27

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.