# Prove language is not regular? [duplicate]

I know how to use the pumping lemma to do so, but I don't think that can be used for this language:

$$L = \{x \in \{0,1\}^* : \text{no prefix of x has more 1's than 0's}\}.$$

What other method can I use to prove this?

• The pumping lemma should be enough. Think about what the prefix condition tells you about the whole string. – David Richerby Oct 27 '13 at 19:48
• can I use a pumping length p? or is that too general? If can use p you could just do (0^p-1)1 and pump 1 p times – user11006 Oct 27 '13 at 21:22
• That looks like the right approach, yes. If the language was regular, there would be a pumping length. The pumping length is essentially the number of states of some automaton that accepts the language, so you can't choose it: that means you have to be general and just let it be $p$. – David Richerby Oct 28 '13 at 0:26
• I suggest you have a look at our reference question: cs.stackexchange.com/questions/1031/…. – Yuval Filmus Oct 28 '13 at 5:03

Hint: use $0^n1^n$ for large enough $n$.
Another approach is to use the Myhill-Nerode criterion, say with the words $0^n$.