0

{ambnci | m > n + i}

I've been trying to figure this out for two hours. This is what I have so far.

//To start with as many a's as you want:  
S => a | aA | aS   
//To ensure an a gets added each time a b or c does so there is always at least 1 more a than b's plus c's.  
A => aBb | aaBbCc | aCc   
B => aBb | lambda  
C => ???

I know this is nowhere near correct, which is why I'm asking for help/hints.

Thanks.

woodenToaster
  • 254
  • 1
  • 5
  • 12

2 Answers2

1

Your grammar is not correct.

Read Tips for creating “Context Free Grammar” and linked answers to it, Grammar of your language is

S --> aSc | B    // for every `c` there must be a `a`
B --> aBb | A    // for every `b` there must be a `a`
A --> aA  | a    // generate extra `a`
Community
  • 1
  • 1
Grijesh Chauhan
  • 55,177
  • 19
  • 133
  • 197
0

Build it up from the inside out:

  • B → aBb | ε        -- matches aibi
  • C → aCc | B       -- matches ai+jbicj
  • S → aC | aS       -- add at least one more a on the front

This is not minimal -- you could do it with 5 rules and 2 non-terminals.

Chris Dodd
  • 111,130
  • 12
  • 123
  • 212