Context Free Grammar for unequal number of symbols

1
votes

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?

2
context-free-grammarlexicalcontext-free-language
Yes, I do have an idea. Hint: two unequal sets are just two equal sets separated by multiple of one of the elements. – John Dvorak

2 Answers

2
votes

Edit : (corrected) Something like the following forces to have at least one 0 more than 1's:

S->T0S | T0T
T->0T1T | 1T0T | ε

so now, it shouldn't be too hard to add one more 0 by repeating same pattern ...

doing so the following grammar answers the problem: 

S->T0S | T0T
T->0T1T | 1T0T 
T->U0T | U0U
U->0U1U | 1U0U | ε
1
votes

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.