-1
$\begingroup$

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

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

2 Answers 2

2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ looks fine to me too $\endgroup$
    – Infinity
    Apr 28, 2019 at 16:42
0
$\begingroup$

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.

$\endgroup$
9
  • 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, 2019 at 23:18
  • $\begingroup$ @gnasher729 maybe because you are more proficient at it? $\endgroup$
    – Infinity
    Apr 29, 2019 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, 2019 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, 2019 at 4:26
  • $\begingroup$ @Infinity Yes, I am a cs undergrad at IITB. $\endgroup$
    – SiluPanda
    Apr 29, 2019 at 10:12

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.