Context Free Grammar - set of strings in which the number of 1’s is one more than the number of 0’s

Question

I am attempting to write a context-free grammar for L = the set of strings in which the number of 1’s is one more than the number of 0’s. Thus, 1011010, 0001111 etc. are in L, but strings like 001101, 000011 etc. are not in L.

So far, I have a context-free grammar for L = the set of strings in which the number of 1’s is more than 0’s:

S → TS|1T|1S

T → TT|0T1|1T0|ε

How can I change this so that the number of 1's is ONLY 1 more than the number of 0's?

Answer 1

Based on templatetypedef's answer, you can find such grammar at https://math.stackexchange.com/questions/2207708/context-free-grammar-for-language-a-b-where-the-number-of-as-the-number

So basically the final grammar would be:

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

Answer 2

Consider:

S → T1T

T → 10T | 01T | 0T1 | 1T0 | ε

Then you start with a single1 (S → T1T), and always add the same number of 0's and 1's (in any possible arrangement) with each application of T.

Answer 3

As a hint, if you have a string with exactly one more 1 than 0, there's some way to write it as w1x, where w and x have exactly the same number of 0s and 1s. If you can find a CFG that generate strings with the same number of 0s and 1s with start symbol X, then you can add a start symbol S and production S → X1X and you should be good to go.