I am trying to translate the following description "all strings of 0s and 1s with at least as many 0s as 1s" into a language.
I thought about {L= 0^n1^n | n>0} but what about the "at least" part? Does that mean I could have more 0s than 1s? (Ex. 000011) (or maybe {L = 0^j1^k | j>k, j,k >0} ? ) I'm not entirely sure how that would work, so any help would be appreciated :)
(btw I'm doing this so I can prove it's not regular with pumping lemma, any tips are welcome lol)
There is not a very satisfying set-builder notation for this. Let #k(w) be the number of occurrences of the symbol k in the string w, where w is a string over some alphabet including symbol k. Then your language is { w in {0, 1}* | #0(w) >= #1(w) }. I am not sure writing it down this way helps much.
To prove the language isn't regular, I'd recommend using the pumping lemma for regular languages or the Myhill-Nerode theorem directly from the plain description. For the pumping lemma, choose 1^p 0^p and argue that pumping up adds too many 1s. To use Myhill-Nerode, choose the sequence 1, 11, ..., 1^k, ..., and argue that the shortest string that can be appended to 1^k to get a string in your language is 0^k, meaning all 1^k are distinguishable.