Search code examples
context-free-grammarlexicalcontext-free-language

Context Free Grammar for unequal number of symbols

I'm aware of how it is possible to construct a context free grammar with the same number of two given elements ie. if we use {0,1}

S->SS
S->0S1
S->1S0
S->ε

I am however struggling to find a way to construct a grammar that has a given amount of one element more than another. ie. consistently two more 0s than 1s. Does anyone have any ideas of how to construct such a grammar?

Solution

  • I worked out a nice answer to this:

    S->P0P0P
P->PP
P->0P1
P->1P0
P->ε

    It should come up with a string of two more 0s than 1s, and can be easily extended to greater numbers.