1

Language: {a^m b^n : m ≤ 2n}

If someone could give advice on how to approach this to construct the grammar as well as a solution that would be great and much appreciated!

Schwarz
  • 395
  • 4
  • 18
  • Read [Construct grammar given the following language `{a^n b^m | n,m = 0,1,2,…,n <= 2m}`](http://stackoverflow.com/questions/15559324/construct-grammar-given-the-following-language-an-bm-n-m-0-1-2-n-2) – Grijesh Chauhan Apr 23 '14 at 06:53

1 Answers1

1

Some hints:

  1. Start with a grammar for { anbn | n in N }.

  2. The grammar you built in part (1) probably worked by laying down a's on one side of the string and b's on the other. That way, there end up being the same number of a's and b's. Try modifying the grammar so that you put down either one a or two a's each step.

Hope this helps!

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
  • Thanks for the advice! Care to verify for me if it is correct? I believe then this is the right answer: S -> e S -> SaSaSbS S -> SbSaSaS S -> SaSbSaS S -> SaSbS S -> SbSaS – Schwarz Apr 22 '14 at 22:45
  • @Schwarz That doesn't seem like it works because it allows the a's and b's to be arbitrarily intermixed. There's a much simpler solution that keeps all the a's at the front and the b's at the back. – templatetypedef Apr 22 '14 at 23:13
  • Sorry I misunderstood the question and thought it was the {a, b}*. But now I believe this is correct: S -> e S -> aSb S -> Sb – Schwarz Apr 22 '14 at 23:31