I need a Context Free Grammar for this language. I could come up with this solution:

S -> AB
A -> aA | ε
B -> bbbB | ε

But, this grammar is clearly wrong, since the number of a's can still exceed the number of b's. How do I draw a link between the two variables A and B such that $n\leq m+3$?

P.S. It is a humble request to anyone who downvotes this question to please specify the reason in the comments below

  • 2
    $\begingroup$ Create up to 3 a’s. Then repeatedly either create ab or b. $\endgroup$ – gnasher729 Apr 28 '19 at 15:14
  • $\begingroup$ @gnasher729 sorry I couldn't get it, could you write an answer please? $\endgroup$ – Infinity Apr 28 '19 at 15:30

Based on gnasher729's comment, I came up with the following CFG that I believe meet the requirements:

$$ S \to AAAB \\ A \to a \;|\; \varepsilon\\ B \to aBb \;|\; Bb \;|\; \varepsilon $$

  • $\begingroup$ looks fine to me too $\endgroup$ – Infinity Apr 28 '19 at 16:42

It is hard to come up with a CFG directly. A better approach can be, making a PDA and converting the PDA to CFG. Refer to this answer.

  • 1
    $\begingroup$ Huh? Took me 10 seconds to write down how to do it, and Acid probably not more than a minute to do it (and most of that time figuring out how to type an epsilon). $\endgroup$ – gnasher729 Apr 28 '19 at 23:18
  • $\begingroup$ @gnasher729 maybe because you are more proficient at it? $\endgroup$ – Infinity Apr 29 '19 at 3:33
  • $\begingroup$ @gnasher729 in case anyone of you has downvoted this question, please read the post again and do the needful $\endgroup$ – Infinity Apr 29 '19 at 3:37
  • $\begingroup$ @gnasher729 I just pointed out a procedure to go about it. I personally had a hard time coming up with the grammars directly in the past. $\endgroup$ – SiluPanda Apr 29 '19 at 4:26
  • $\begingroup$ @SiluPanda hello sir! you are from iit b? $\endgroup$ – Infinity Apr 29 '19 at 8:04

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.