CODEWITHSUNDEEP
context-free-grammarautomatacontext-free-language
Schwarz
Schwarz

Reputation: 395

Construct a context-free grammar from this language

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!

Upvotes: 1

Views: 534

Answers (1)

templatetypedef
templatetypedef

Reputation: 372664

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!

Upvotes: 1

Related Questions