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
  • 264
  • 1
  • 4
  • 13

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
  • 57,103
  • 20
  • 141
  • 208
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
  • 119,907
  • 13
  • 134
  • 226