CFG for $n_b = n_a + n_c$

85 Views Asked by At

I am trying to figure out the CFG of the given language.

The language is:

(number of b) = (number of a) + (number of c)

eg: bbac, bbbabcac ...

When I only consider the (number of b) = (number of a). I find a CFG something like this.

S -> aSbS | bSaS | €

But I cannot upgrade this CFG to the triple equality.

Any help is appreciated.

1

There are 1 best solutions below

0
On BEST ANSWER

How about:

\begin{align} S &\gets XSbS \mid bSXS \mid \varepsilon\\ X &\gets a \mid c \end{align}