2
$\begingroup$

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.

pda

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.

1 Answers 1

3

How about

S ::= aSb | A | B A ::= a | Aa B ::= b | Bb 
  • 0
    @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.2011-09-18