# Implement Context-Free Grammar for $L=\{a^n b^m \mid n \neq 2m\}$

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?

• If n \neq 2m then n is equal to either 2m+k or 2m-k for some positive integer k. Try working from that. – quicksort Dec 5 '16 at 19:08
• 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. – 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