# Need to create CFG that requires sum of other letters

I have a homework assignment that requires me to create CFG $$G$$ for

$$L = \{a^i b^{i+j+k} c^j d^k\}$$

so that it can accept words like ab, aaabbbbd, abbbcd, but it should not accept abba, aabbbbbc, or abc since the number of b must be the number of a+c+d.

I need CFG of L(G)

• I tried using chatgpt but the answers are not correct as I cross checked them with both gpt and myself.
• I tried to cross check this pdf but they are not as complex as my question.
• There is also a solution on chegg I can't see the whole solution as I don't have a subscription, but the final solution is also wrong as I checked it with both chatgpt and myself.

The best one i came up with this grammer but it doesn't feel right since it does not have corelation between b c and d.

1. attempt:

S → AB
A → aAb | ε
B -> bCEdD
C -> bB | ε
D -> dD | ε
E -> bEc | ε

2. attempt :

S → AB
A → aA | ε
B → bBC
C → cC | Cd | ε
D → dD | ε


Is it possible to do it with cfg and how?

– D.W.
Mar 15 at 17:09
• I have already answered this question in the "Asnwers" section. I have problems understanding the accepted words, even after reading the proof of correctness @D.W. Mar 15 at 17:55

Use the nesting structure of the language to obtain a context-free grammar.

$$a^i\, b^{i+j+k}\, c^j d^k = a^i b^i\, b^k b^j c^j d^k$$

We can see that the language is the concatenation of strings of the form $$a^i\, b^i$$ and strings of the form $$b^{j+k}\, c^j d^k$$ which each separately form context-free languages.

• The part I don't understand is when I use a cfg like : - S → ABcd - A → aAb | ε - B → bBc | ε - C → cCd | ε seems to be correct and also produces what I'm asking for, but it also accepts words like "abba, aabbbbc or abc" which I want to use specifically and only for the words I'm describing, so if the language doesn't have that, that's the part I don't understand Mar 15 at 16:38
• Respect the nesting structure. Generate "bc"-pairs inside the "bd"-pairs. Mar 15 at 23:23
• I also add this cfg to the main question but here's what i did : S → AB ---- A → aAb | ε ---- B -> bCEdD ---- C -> bB | ε ---- D -> dD | ε ---- E -> bEc | ε. I can't solve that point i don't know how to add bc in bd because there's also an bcd combination that i need to make recursive. Mar 16 at 9:00

$$S\rightarrow AD$$
$$A\rightarrow aAb,\varepsilon$$
$$D\rightarrow bDd, C$$
$$C\rightarrow bCc, \varepsilon$$.

In this solution I divided the word into a prefix of $$a^ib^i$$ and a suffix of $$b^{j+k}c^jd^k$$. The latter part is generated by building $$b^kCd^k$$ and then replacing $$C$$ with $$b^jc^j$$.

• Is the " , " the same as the " | " or does this symbol have a different purpose? Mar 16 at 16:33
• yes it is the same, I just mean different choices of the right side. Mar 16 at 16:41