-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

Improve this question
$\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

Reset to default
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 $$

Improve this answer
$\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.

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