I need help with this homework problem (Formal languages and Automata grad-level course).
Find a CFG for this language: $$ \Sigma =\{0,1\}$$ $L$ are all the words $w\in\Sigma^*$ that in every prefix of $w$ there are at least as many $0$’s as there are $1$’s.
My attempt: After much trial and error, I came up with this CFG: $$ S\rightarrow 0S|01S|\epsilon|0$$ The idea I thought about is that for every $1$ added to S (they are added at the end of a prefix each time), a $0$ should be added too. I don't have enough intuition to check my solution so I'm not sure at all that this is true. In general I am lacking intution and the right approach to these problems.
I would appriciate it if someone could show me the right way to approach this problem.
Thank a lot
Edit: This is obviously not true, it obviously doesn't cover all words in this language (only those who look something like this: $001010001010101....$. I have no idea how to make this cover all the language..
I think: $$S\to K1|0S|\epsilon$$ $$K\to KK1|0$$ will work. K represents you 'owe' a one.
I think showing that anything you get will be in the language, is pretty straight forward since you can't add a 1 without having a 0 behind it.