I am trying to implement a context-free grammar for $L=\{a^n b^m \mid n \neq 2m\}$.

I have a difficulty trying to implement it because I don't know how to ensure that $n \neq 2m$.

I can easily implement $n=2m$ but the other way around doesn't seem intuitive. How can I approach this problem?

  • 4
    $\begingroup$ If n \neq 2m then n is equal to either 2m+k or 2m-k for some positive integer k. Try working from that. $\endgroup$ – quicksort Dec 5 '16 at 19:08
  • 1
    $\begingroup$ Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$ – Evil Dec 5 '16 at 19:42

Hint: A string of the form $a^nb^m$ where $n \neq 2m$ can be either

  • A string with too many $a$'s, or
  • A string with too few $a$'s

Create production rules for each of these cases.

| cite | improve this answer | |

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.