Find a CFG for L = { a^nb^m : n != m } This question is upcoming for my midterm and I can't figure it out. My professor broke it down in two statements (n>m) and(m>n) and left us at that. 
Find a context free grammar for $L = \{ a^n b^m : n \neq m \}$
 A: Hint:


*

*$\{a^nb^m \mid n < m\} = \{a^nb^n \mid n \in \mathbb{N}\} \circ \{b^k \mid k \geq 1\}$

*$\{a^nb^m \mid n > m\} = \{a^k \mid k \geq 1\} \circ \{a^nb^n  \mid n \in \mathbb{N}\}$

*Assuming that $X$ generates $\{a^nb^n\}$, start with $S \to XB \mid AX$.


I hope this helps $\ddot\smile$
A: Here is the solution:
(1) $S → AX \mid XB$ 
(2) $X → aXb \mid e$
(3) $A → aA \mid a$
(4) $B → bB \mid b$
(1) means the answer is in two states: number of $a$'s larger than number of $b$'s or number of $b$'s larger than number of $a$'s. So the problem solved!
A: yes,the idea to form grammars for this falls in two divisions 1)nm
so lets define the grammar for each individually and combine.
S -> X |  Y
X  -> aXb  | Xb | b
Y  -> aYb  |  aY |a   
A: You have two cases like your professor stated: $n > m$ and $n < m$. Let $x \to c_1$ and $x \to c_2$ be two rules that initiate the two cases, i.e. $x$ is the start variable. Then for example, for $n > m$ this is handled by $c_1$ and the context free grammar rules to generate it are $c_1 \to a$, $c_1 \to a c_1 b$, and $c_1 \to a c_1$. Similarly for $c_2$ to handle the case $n < m$.
A: In this problem, strings start with a number of a's followed by the number of b's. there may be two cases

*

*number of a's are greater than the number of b's , so we can assume that
i) number of a's are equal as number of b's and after that we have to generate at least one extra a in the string
so productions are
S--> aSb |  A
A--> aA|a

*number of b's are greater than the number of a's , so we can assume
i) number of a's are equal as number of b's and after that we have to generate at least one extra b in the string
so productions are
S--> aSb |  B
B-->bB|b
Hence Grammar productions are
S-->aSb|A|B
A--> aA|a
B-->bB|b

A: As per the given problem we have two cases i.e.

*

*either the number of a can be greater than b (when n > m)

*or the number of b can be greater than a (when m > n).

The minimum string that need to be generated is either a or b.
Then this production rule must satisfy all the conditions:
S -> Sa | Sb | E | a | b

