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
    This will accept if my input is 'a' but the condition is both m,n>02011-09-18
  • 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