# Unable to construct Context-free Grammar from Pushdown Automaton

I have a problem in constructing a Context-free Grammar for the Language $$L = \{a^mb^n : m≠n,m>0,n>0\} .$$ Though I can able to construct a Pushdown Automata.

I can construct a CFG, but it accepts both $m \neq n$ and $m=n$. My CFG is:

$S \to aS/Sb/aSb/aab/abb$.

I cannot able to consturct the CFG to accept for $m \neq n$ alone.

-
this reads like a homework question, please tag it as homework if it is. –  Artem Kaznatcheev Sep 18 '11 at 16:07
I made your title grammatically correct. Please do the same with the text of your post. –  Did Sep 18 '11 at 16:44

## 1 Answer

How about

S ::= aSb | A | B
A ::= a | Aa
B ::= b | Bb

-
This will accept if my input is 'a' but the condition is both m,n>0 –  EAGER_STUDENT Sep 18 '11 at 16:02
@EAGER_STUDENT it is trivial to modify Henning's answer to make both m,n > 0. Just add T ::= aSb as the first production rule (and always start at T, this will force us to have at least one a and b. –  Artem Kaznatcheev Sep 18 '11 at 16:06