1
$\begingroup$

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.
  • Also researched multiple sources but did not found the answer.

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ cs.stackexchange.com/q/18524/755 $\endgroup$
    – D.W. ♦
    Mar 15 at 17:09
  • $\begingroup$ 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. $\endgroup$
    – Sefa Kalkan
    Mar 15 at 17:55

2 Answers 2

Reset to default
0
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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 $\endgroup$
    – Sefa Kalkan
    Mar 15 at 16:38
  • $\begingroup$ Respect the nesting structure. Generate "bc"-pairs inside the "bd"-pairs. $\endgroup$
    – Hendrik Jan
    Mar 15 at 23:23
  • $\begingroup$ 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. $\endgroup$
    – Sefa Kalkan
    Mar 16 at 9:00
0
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Is the " , " the same as the " | " or does this symbol have a different purpose? $\endgroup$
    – Sefa Kalkan
    Mar 16 at 16:33
  • $\begingroup$ yes it is the same, I just mean different choices of the right side. $\endgroup$
    – Narek Bojikian
    Mar 16 at 16:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.